FC Brentford

Paul Smith begann seine Profilaufbahn bei Charlton Athletic. Bei dem Verein aus dem Osten Londons kam er jedoch nicht zum Einsatz und wechselte daher bereits 1999 zu Carshalton Athletic einem unterklassigen Verein aus dem Süden Londons. Im August 2000 wechselte Smith zum FC Brentford, einem Verein aus dem Westen Londons. Brentford spielte zu diesem Zeitpunkt in der dritthöchsten englischen Spielklasse. Paul Smith kam hier erstmals regelmäßig zum Einsatz und belegte mit seinem neuen Verein am Saisonende Platz 14 von 24 Mannschaften. Die Saison 2001/02 verlief für Brentford sehr erfolgreich. Am Ende der Spielzeit stand der Verein auf Platz 3, verpasste allerdings in den anschließenden Play-offs den Aufstieg. In den folgenden beiden Spielzeiten konnte der FC Brentford an diese Leistung nicht mehr anknüpfen und fand sich mit den Plätzen 16 und 17 in den Niederungen der Liga wieder.

FC Southampton

Aufgrund finanzieller Problem sah sich der Verein gezwungen Paul Smith im Januar 2004 für ca. £500,000 an den FC Southampton zu verkaufen. Smith konnte sich bei dem Verein aus Southampton jedoch keinen Stammplatz erkämpfen, da Antti Niemi häufig den Vorzug erhielt.

Nottingham Forest

Im Juli 2006 wechselte Paul Smith für ca. £500,000 zu Nottingham Forest und unterschrieb dort einen Dreijahresvertrag. Seine erste Saison 2006/07 verbrachte er als Stammtorhüter in der Football League One. Am Ende der Saison stand Nottingham auf Platz 4, mit nur 3 Punkten Rückstand auf den direkten Aufstiegsplatz 2. In den Play-offs musste Forest dem FC Blackpool den Vortritt lassen. In der Saison 2007/08 gelang dafür mit Platz 2 der Aufstieg in die Football League Championship. Paul Smith spielte unterdessen eine gute Spielzeit und wurde zum besten Torhüter der Liga ausgezeichnet. Mit Beginn der Football League Championship 2008/09 spielte er damit eine Spielklasse höher. Vor dem Saisonstart unterschrieb er einen neuen 2-Jahres-Vertrag. Bereits im Oktober 2008 kam jedoch Lee Camp auf Leihbasis vom Ligarivalen Queens Park Rangers zu Forest und verdrängte Paul Smith von seinem Platz zwischen den Pfosten. Der neue Trainer Billy Davies setzte in der Folgezeit auf den stark spielenden Camp, so dass Paul Smith in der Saison 2009/10 nur auf vier Pflichtspieleinsätze kam. Trotzdem verlängerte er im Verlauf des Jahres seinen Vertrag bis 2012.

Am 8. März 2011 wechselte er auf Leihbasis zum Ligarivalen FC Middlesbrough und bestritt bis Saisonende zehn Ligaspiele für den Zweitligisten.

Southend United

Nachdem sein Vertrag in Nottingham nicht verlängert worden war, wechselte er am 20. August 2012 zum englischen Viertligisten Southend United.