Brankářská jednička anglické reprezentace přišla do Tottenhamu v létě 2004 z Leeds United. Hráč narozený v Beverly odehrál za Leeds 119 utkání a svůj debut si odbyl na hřišti Chelsea už v roce 1998. Opravdu se světu ukázal ale až v sezóně 2000/01 kdy odehrál 24 zápasů včetně startů v Lize Mistrů proti Besiktasi, Barceloně, Realu Madrid a dvakrát proti Laziu Řím. Produkt akademie Leeds pevně odsunul ze hry jedničku Nigela Martina na začátku sezóny 2002/03. Paul měl svůj debut v Anglické reprezentaci při poločasovém střídání proti Austrálii v únoru 2003. Nicméně si nezachytal až do Září 2004, když na pozici jedničky nahradil Davida Jamese a tuto pozici si drží doteď. Za sezónu 2004/05 v Tottenhamu nasbíral 44 startů dokud si v zápase proti Aston Ville v květnu nezranil koleno, které přineslo náhlý pád jeho kariéry. Za tuto sezónu si díky mnoha příznivcům vytvořil fantastický vztah s fanoušky Tottenhamu zvláště po konci Park Lane. Robinson má na svém kontě dokonce i gól, když za Leeds vyrovnal proti Swindonu v druhém kole Carling Cupu v Září 2003. Formu si udržel až do sezóny 2005/06 a díky tomu se stal Anglickou jedničkou na MS 2006 v Německu, kde odehrál všechna utkání.