Paul Sorvino werd geboren in het New Yorkse stadsdeel Brooklyn, als de zoon van Ford en Marietta Sorvino. Als jongeman volgde hij lessen aan de Lafayette High School en de American Musical and Dramatic Academy. Na zijn studies ging hij aan de slag als tekstschrijver in een reclamebureau. Gedurende 18 jaar volgde hij stemlessen en uiteindelijk besloot hij zijn kans te wagen in het theater. In 1964 debuteerde hij op Broadway met de musical Bajour. Zo'n zes jaar later veroverde hij zijn eerste filmrol, in de komedie Where's Poppa? met George Segal in de hoofdrol. Later was hij ook even te zien in de film The Panic in Needle Park, een drama met een jonge Al Pacino als hoofdrolspeler.
Sorvino bleef theater en film combineren. Vaak bleven zijn filmbijdrages beperkt tot bijrollen. Zo speelde hij een communist in de film Reds van Warren Beatty. In 1990 vertolkte de Italo-Amerikaanse acteur maffiabaas Paul Cicero in de alom geprezen misdaadfilm Goodfellas van regisseur Martin Scorsese. Hij speelde in die film aan de zijde van onder meer Robert De Niro, Ray Liotta en Joe Pesci. Een jaar later werd Sorvino bij het grote publiek bekend als Sergeant Phil Cerreta dankzij politieserie Law & Order.
In 1995 kroop Sorvino in de huid van politicus Henry Kissinger in de biopicNixon van Oliver Stone. Op de set uitte hij naar verluidt kritiek op hoofdrolspeler Anthony Hopkins. Sorvino vond dat de stem van Hopkins niet op de stem van diens personage Richard Nixon leek. Sorvino maakte hem dat duidelijk, waarna Hopkins het filmproject dreigde te verlaten.
Hij was ook de oprichter van de Paul Sorvino Asthma Foundation, een organisatie voor astmalijders. Hij verkocht pastasausen via het bedrijf Paul Sorvino Foods.
Paul Sorvino was de vader van actrice Mira Sorvino. Hij stierf op 83-jarige leeftijd in de Mayo Clinic in Jacksonville.[1]
Sorvino met Mitzi Hoag in de tv-serie We'll Get By (1975)
Where's Poppa? (1970) - Eigenaar van de woning van Gus en Grace