After just being discharged from the United States Marines, Paulie Provenzano returned to his home in Brooklyn, where he attempted to join the mafia. They rudely rejected him after discovering he was a mutant with the ability of complete invulnerability, and attempted to murder him. After taking out the goons, Paulie was invited by Jean Grey to join her interim X-Men in order to stop Magneto's madness. Often cracking jokes and flirting with the female members of his team, particularly Frenzy and Dazzler. He also had a rivalry with Northstar as he was extremely uncomfortable with homosexuals.
The team had little time to train but gambled that their unfamiliarity would be enough of an edge to free Xavier and stop Magneto. Arriving on Genosha, the team confronted Magneto. Overconfident, Paulie told Magneto he wasn't scared of 'some guy wearing a bucket on his head'. Magneto attempted to manipulate the iron in Paulie's blood, but it was ineffective due to his invulnerability. However, it did not keep him from being lifted off the ground.
During their battle with Magneto, Paulie immediately created a diversion for his teammates when he taunted Magneto himself. Magneto then levitated Paulie into space, coldly asking Northstar if he thought he was fast enough to save his teammate before he suffocated. Northstar was barely able to reach Paulie in time and took him to a nearby US warship. Paulie was shocked and a bit uneasy that Northstar had given him mouth to mouth, but thanked Jean-Paul. After the battle, Paulie declined to remain an X-Man and left the X-Mansion to journey on his own.
Paulie was eventually kidnapped by the Weapon X program and was executed at the Neverland Ranch.
It was later stated that Omerta did not die. His actual activities and his mutant-situation after the M-Day are unknown.
Paulie was planned to be in the Neverland Camps in Weapon X, and supposedly died, but due to a coloring mistake, it cannot be confirmed that it was him in the gas chambers after all. Also, Paulie never took the name "Omerta" in canon, but that was his original name to begin with.