Passato professionista nel 2002 con la squadra portoghese ASC-Vila do Conde, nel 2004 si trasferisce alla squadra L.A.- Pecol, e comincia a cogliere risultati importanti, tra i quali due tappe del Giro del Portogallo, la vittoria nel campionato nazionale a cronometro ma soprattutto il 2° posto alle Olimpiadi di Atene, battuto solo da Paolo Bettini.
Grazie a questi risultati ottiene un buon ingaggio in Spagna nella Liberty Seguros, però nel primo anno non riesce a ripetere gli ottimi risultati dell'anno precedente. Nell'estate 2006 il suo nome finisce in un primo momento nella lista di atleti coinvolti nello scandalo doping dell'Operación Puerto e questo gli costa la partecipazione al Tour de France.
Scagionato dalle accuse, Paulinho riprende l'attività e disputa una buona Vuelta di Spagna con la neonata Astana Team, che ha preso il posto della Liberty, cogliendo una bella vittoria nella 10.a tappa con arrivo a Santillana del Mar e terminando al 16° posto nella classifica finale, segnalandosi anche per il prezioso lavoro per il suo capitano Alexandre Vinokourov, vincitore della corsa.