Spring 1942 Anastasia, who was under constant scrutiny from the FBI and local law enforcement secretly ordered the murder of associate Anthony Romeo. Like Reles, Romeo had been arrested and was talking to authorities to implicate Anastasia in several murders. By the end of June, Romeo’s body was found beaten and shot multiple times near Guyencourt Delaware.
With the start of World War II, Anastasia reportedly became the mastermind behind a plan to win Luciano freedom from prison in exchange for supplying the United States government with inside information from his contacts in Sicily. He also suggested he could protect the eastern waterfront from German attack. As a part of the effort, Anastasia joined the United States Army although many speculate he did this to escape criminal investigations, he maintained he was doing his part to secure the borders by training longshoremen on the coast in Pennsylvania. As a reward for his efforts Anastasia was granted citizenship in the United States. He was no longer illegal, and after his honorable discharge from the Army in 1944 moved his family to a mansion in Fort Lee, New Jersey.
Despite working closely with Luciano and Costello, Anastasia was the underboss of the Mangano family. Boss of the family Vincent Mangano resented the relationship Anastasia had with the two men and was particularly upset Luciano and Costello didn’t ask for his permission before requesting Anastasia’s services. This and several other small disputes led to Mangano and Anastasia almost coming to blows several times. In early 1951 Vincent Mangano went missing. He was never heard from again. On April 19, 1951 the body of Phillip Mangano, Vincent’s brother was found shot three times floating in a wetland outside of Bergen Beach, Brooklyn. It is widely assumed Anastasia had enough and disposed of the Mangano brothers but no charges were ever filed.
As underboss, and with Mangano out of the picture, Anastasia became the new boss of the Mangano family renaming it the Anastasia family (the future Gambino family). He was a ruthless boss having once killed an informer who had nothing to do with his family just because he “didn’t like stool pigeons”. In a similar situation in March 1952 Anastasia was watching television where a young man from New York Arnold Schuster identified a fugitive bank robber Willie Sutton, resulting in Sutton’s arrest. When Anastasia saw this, he allegedly said: “I can’t stand squealers! Hit that guy!” Days later, gunmen shot Schuster to death on a street in Borough Park, Brooklyn. No one was ever arrested for the slaying.
Around the same time Vito Genovese, a powerful mobster in his own right was vying for the top spot of the Costello family after Luciano was deported. His power was limited as Costello and Anastasia had control of the commission, but after hearing of the slaying of Schuster, Genovese felt he had an opening. To kill Costello, he would need to eliminate Anastasia so he began to paint a picture of Anastasia being unstable, and unpredictable. He spoke about Anastasia bringing about unnecessary attraction to the mafia during a time where the FBI was looking for anything to bring about indictments. He soon had the ear of Anastasia capo Carlo Gambino, and Luciano friend Meyer Lansky who was growing more upset with Anastasia for muscling in on his Cuba casino operations.
Soon after gaining support from other top mobsters, Genovese went to the commission and accused Anastasia of selling memberships to his family. This was a huge accusation that the commission took seriously. In an effort to drive a wedge between Costello and Anastasia, Genovese also claimed Anastasia was plotting against Costello. With their relationship in question, Genovese felt comfortable moving against Costello. On May 2, 1957 gunmen, later identified as Vincent ‘The Chin” Gigante shot and wounded Costello outside his apartment building. The near death experience convinced Costello life was more important. He stepped in front of the commission and retired giving Genovese control of the family.
Genovese wasn’t finished with his rise to the top of the commission. To make Anastasia appear more unstable, Genovese spread the word that Anastasia hired The Chin to shoot and miss Costello. Of course it was Genovese who hired Gigante, Costello believed the ruse and gave his approval for Genovese to move against Anastasia.
In the end, Anastasia’s own routine gave Genovese gunmen the opportunity to end his reign. On the morning of October 25, 1957 Anastasia entered the Park Sheraton Hotel barber. Joe Bocchino, who had been shaving and cutting Anastasia’s hair for years, draped a candy striped barber’s cloth over Anastasia and began cutting his hair. A manicurists sat next to the chair and worked on the bosses fingernails. A shoeshine boy began polishing Anastasia’s brown shoes. It was the same time and same service Anastasia had every other day for years.
Shortly after 10:15 a.m. with Anastasia dozing in the chair, his eyesclosed, two men quietly walked into the barber shop. They drew their .38 caliber pistols and waved the men and boy away from Anastasia’s chair. As they scattered Anastasia opened his eyes and lifted his hand in a defense as both men open fired. According to reports Anastasia let out a roar and leaped from the chair reaching for the two gunmen. He spun around after being hit in the hand, wrist, and hip. A bullet then ripped into his back causing him to fall to the floor at the base of the barbers chair. One of the gunmen is said to have calmly walked up to Anastasia, and fired the fatal round to the back of his head. Both gunmen disappeared as quickly as they appeared and although they were never apprehended, the gangland consensus is it was brothers Larry and Joe Gallo who committed the murder after being contracted by Don Vito Genovese. With Anastasia dead, capo, Carlo Gambino was awarded the Anastasia family from the commission with Genovese sitting firmly in control.