Destiné à devenir chanteur d'opéra, Paul Sorvino se tourne finalement vers l'art dramatique qu'il étudie à la New York Music & Dramatic Academy. Son asthme sévère n'entame en rien sa volonté de jouer la comédie.

L'une de ses premières apparitions à l'écran, il la doit à Jerry Schatzberg qui lui donne sa chance dans Panique à Needle Park en 1971. Gérant de casino face à James Caan dans Le Flambeur (1974), il multiplie les seconds rôles dans Les Chaînes du sang (1978), La Chasse / Cruising (1980) où il incarne le supérieur hiérarchique d'Al Pacino, Reds (1981) ou encore That championship season (1982).

Ses origines italiennes et sa forte stature lui valent de figurer dans le quatuor de tête des Affranchis en 1990. La même année, il se trouve de nouveau un rôle de mafieux dans l'adaptation de la bande dessinée Dick Tracy signée Warren Beatty, qui le dirigera dans deux autres longs métrages (Bulworth et L'Exception à la règle).

Interprétant de temps à autre des personnages antipathiques comme un acteur pro-nazi dans The Rocketeer (1991) ou un impitoyable patriarche dans Romeo + Juliette (1997), Paul Sorvino aime également à camper des éminences grises comme le secrétaire d'Etat Henry Kissinger dans Nixon (1996) et à user de son autorité dans les films d'action Wanted recherché mort ou vif (1997) et Piège à Hong Kong (1998).

Dans les années 2000, le père de l'actrice Mira Sorvino s'oriente vers des comédies familiales telles que Spot (2001) et Mambo italiano (2004) et prête sa voix à l'infâme M. Scheck dans le dessin animé Hé Arnold ! (2003). Il retrouve toutefois un rôle ambigu dans le drame Lady chance (id.) face à Alec Baldwin et William H. Macy puis joue à nouveau un mafieux dans le nanar Repo! The Genetic Opera (2008) qui lui permet de mettre en avant ses capacités de chanteur lyrique.

Durant les années 2010, il continue de s'illustrer dans des seconds rôles dans de nombreux projets au cinéma et à la télévision (notamment les séries Bad Blood et Godfather of Harlem), et passe derrière la caméra avec The Trouble with Cali (2012) écrit par sa fille Amanda Sorvino.