Paulie was one of the men who took revenge on the men who assaulted Amerigo Bonasera's daughter, Maria, severely beating the two punks and becoming increasingly respected in the Family. Paulie later sold out to Virgil Sollozzo and called in sick one day, leaving only Fredo to protect the Don, who was shot buying fruit. Shortly after, he alerted Sergeant Joe Galtosino to a Corleone party at Rosa's, but this attack floundered, resulting in Galtosino's death.
Paulie's treachery was later found out, but it was not immediately acted upon, as he was called to assist Clemenza and Aldo Trapani in blowing up The Roost, a Tattaglia bar. He ran away from the conflict, which sealed his fate. Also, whilst being supplied prior to the raid at The Albatross Grill, he had been heard being instructed on how to make the raid fail. He had also been involved in strong-arming the chef there for the Tattaglias, but it was foiled by Trapani.
Clemenza told Paulie to drive to a shipping yard in Brooklyn after finding an appropriate location to 'go to the matresses', where he was executed by three shots to the head. Paulie's role as soldati was filled by Rocco Lampone and his Brooklyn apartment was given to Aldo Trapani.
.In the game's canon, Paulie was alerted to his impending execution by the sound of Aldo Trapani's gun cocking, and he fled the car into the shipping yard. Trapani hunted down his former associate and executed him for his treachery.
Originally, Paulie was going to be played by Robert De Niro, but he was traded to another production for Al Pacino. Ironically, this meant that De Niro would now be able to appear in his Oscar winning performance as the Don in The Godfather: Part Two.