At the Havana Conference Genovese revealed his ambitions to take over the syndicate. He lobbied to get Luciano to retire, asking Lucky in private if it might be time to step down while at the same time polling the other conference attendees to see if he could get them to vote Luciano out. Genovese also proposed that Albert Anastasia, the Lord High Executioner, be eliminated because he had become too "kill crazy." Anastasia had been dropping hints that he was going to put a contract out on Bureau of Narcotics Director Harry Anslinger. Luciano called off the hit on Anslinger and managed to block Genovese's move to kill Anastasia, knowing that he would need the Lord High Executioner's muscle if Genovese ever decided to go to war for supremacy of the New York rackets. The syndicate summit ended, and the mobsters, including Frank Costello, returned home with American officials none the wiser.
Despite his reputation as an able negotiator, Frank Costello was not above using violence when he deemed it necessary, but when he did lash out, he did it his way. As Luciano's acting boss in New York, he sat on the syndicate commission that decided whether certain individuals should be executed. When Abe "Kid Twist" Reles, one of Murder Inc.'s top executioners, started cooperating with authorities, Costello is said to have found out through his police sources where Reles was being kept, the Half Moon Hotel in Coney Island. Despite a cadre of detectives guarding Reles, someone managed to get into his room and push him out a window to his death. The details of the murder remain a mystery, but all those involved at the time agree that it was Costello who pulled the strings to make it happen.
For the most part, Costello depended on New Jersey mobster Willie Moretti and his contingent of 60 leg breakers for muscle. It was a good arrangement for both men until syphilis got the better of Moretti's mental facilities. As a result of his illness, Moretti blathered, sometimes incomprehensibly, before the U.S. Senate Special Committee to Investigate Crime in Interstate Commerce, better known as the Kefauver Committee Hearings after the head of the committee, Tennessee Democrat Estes Kefauver. Moretti was clearly a liability, and a group spearheaded by Vito Genovese insisted that Moretti had to go before he started revealing syndicate secrets. But Genovese, who longed to unseat Costello as boss, had his own agenda. Without Moretti's troops backing him up, Costello would be vulnerable, and Genovese would be able to make his move. But by the time Moretti was assassinated, Costello had forged another alliance, this time with Albert Anastasia, who agreed to put his considerable manpower behind Costello who in turn advised Anastasia on how to kill his boss Vince Mangano and take over as leader of what would become known as the Gambino crime family.
Costello was also called before the Kefauver Committee, and on March 13, 1951, he reluctantly testified. The ABC television network, which had no daytime programming at this point, broadcast committee sessions to a fascinated public eager to see the faces of the secretive Mafiosi. But Costello's was one face viewers did not see, thanks to the appeals of his attorney. Instead, the camera showed only Costello's hands as he endured a barrage of questioning from the five committee members. Costello, perhaps unwisely, tried to spar with the senators, returning their volleys as hard as they were delivered. In the end he was portrayed as a master manipulator who pulled the strings behind the scenes. His appearance before the committee exposed him for what he was and gradually weakened his effectiveness as a mob leader.
On May 2, 1957, a black Cadillac quietly pulled up to the curb outside Costello's Manhattan apartment building just as he was walking in. A 300-pound man emerged from the car, rushed into the lobby, and hid behind a pillar, a gun in his hand. "This is for you, Frank," the fat man shouted. Costello turned toward the voice just as the gun went off. The fat man ran back to the Cadillac, not realizing that the bullet had only grazed Costello's scalp above his ear. The wound was minor and Costello survived, but the incident convinced him that retirement might be in his best interests. The rotund shooter was alleged to be Vincent "Chin" Gigante who immediately went into hiding and lost a considerable amount of weight before turning himself in. Gigante stood trial for the shooting, but when the prosecutor asked Costello on the stand to identify the man who wounded him, the boss obeyed the rules of omerta, the Mafia vow of secrecy and claimed that he had never set eyes on Gigante. As a result, Gigante was acquitted on all charges.
The mob commission allowed Costello to retire quietly and keep the income from his rackets. Waiting in the wings to take his place was Vito Genovese who had been angling for years to become boss of the organization Lucky Luciano had put together. Genovese, who demanded that his underlings refer to him as "Don Vito," was as vicious as he was clever. His goal was to be anointed "Boss of all Bosses."
Joe Valachi, the first Mafia member in America to turn informant, characterized Vito Genovese this way: "If you went to him and told him about some guy doing wrong, he would have the guy killed and then he would have you killed for telling on the guy."