Op clubniveau speelde Sousa voor Benfica (1989–1993), Sporting CP (1993–1994), Juventus (1994–1996), Borussia Dortmund (1996–1998), Internazionale (1998–1999), Parma (2000), Panathinaikos (2000–2001) en Espanyol (2002). Hij won tweemaal de UEFA Champions League, met Juventus in 1996 en met Borussia Dortmund in 1997. De verdedigende middenvelder was lid van de zogenaamde gouden generatie in het Portugese voetbal, waarmee hij in 1989 het WK onder 20 won. Paulo Sousa speelde uiteindelijk 51 interlands en kwam uit voor zijn land op Euro 96 en Euro 2000. Door blessures moest hij op 31-jarige leeftijd een punt zetten achter zijn loopbaan.