Paolo Costoli trat für Rari Nantes Florentia an. Er gewann als Schwimmer insgesamt 19 italienische Meistertitel, davon allein sieben über 1500 Meter Freistil.
1932 bestand das italienische Schwimmteam bei den Olympischen Spielen in Los Angeles aus Giuseppe Perentin und Paolo Costoli. Beide traten über 400 Meter Freistil und über 1500 Meter Freistil an. Über 400 Meter Freistil schieden beide im Halbfinale aus. Jean Taris erreichte als einziger Europäer das Finale.[3] Über 1500 Meter Freistil schied Perentin im Vorlauf und Costoli im Halbfinale aus, auch hier war der Franzose Taris der einzige Europäer im Endlauf.[4] Zwei Jahre später bei den Schwimmeuropameisterschaften 1934 in Magdeburg gewann Taris auf beiden langen Freistilstrecken den Titel vor Costoli.[1] Die 4-mal-200-Meter-Freistilstaffel in der Besetzung Massimo Costa, Giacomo Signori, Guido Giunta und Paolo Costoli belegte wie 1931 den dritten Platz hinter den Ungarn und den Deutschen.[2]
Nach dem Zweiten Weltkrieg war Costoli als Trainer tätig. 1966 befand er sich mit den Olympiateilnehmern von 1964 Bruno Bianchi, Dino Rora und Sergio De Gregorio sowie Amedeo Chimisso, Carmen Longo, Daniela Samuele und Luciana Massenzi auf der Anreise zum 10. Internationalen Schwimmfest des Bremer Schwimmclubs, als der Lufthansa-Flug 005 abstürzte. Die vier Besatzungsmitglieder und alle 42 Passagiere starben.
