Paulinho siirdus 2006. aastal vaid 17-aastaselt Leedu klubisse FC Vilnius, kus pallis kaks hooaega. Seejärel siirdus ta Poolasse LKS Lodzi ridadesse ning pärast viit aastat kodumaal liitus ta Tottenham Hotspuriga.

"Leedus ei olnud mul lihtne kohaneda, sest nii noorelt oli see suur muudatus. Mul oli küll kaheksa-üheksa Brasiilia tiimikaaslast, kuid pärast aastat tahtsin sealt lahkuda, sest pidin taluma tohutult rassismi," sõnas Paulinho Barcelona pressiteenistusele.

"Kui pärast Poolas mängimist kodumaale naasin, rääkisin vanematele, et tahan jalgpalli mängimise lõpetada - ma ei tahtnud, et see võiks uuesti juhtuda."