Costello was born in Calabria, Italy, and in 1895 he boarded a ship to the United States alongside his mother and sister. In the States he grew to become a member of a local gang by the age of 13, and he started using the name of Frank. He continued to commit small crimes and spend amounts of times in jail during his period as a teenager and young adult, and in 1915 he had to serve for 11 months in jail after being found carrying a concealed weapon.
After he got out of jail that time, he began dealing in the underworld, and he teamed up with Lucky Luciano. Together, they prospered in such business areas as bootlegging, gambling and slot machines. Costello was considered by his fellow gangsters as an important link between the Mafia and politicians, judges and police, and he earned the respect of many of his gangmates, including Luciano, as a man who could pay off anyone. He had particularly strong links with Tammany Hall, a Democratic Party organization, and with Big Bill Dwyer.
When Luciano went to prison in 1936, he was sent to Dannemora in upstate New York, almost at the border with Canada. Luciano attempted to rule his crime family from jail, but being so far away, he had to name someone as acting boss, and he chose Costello, with Vito Genovese filling in the role of Underboss. It could be said that the period that Costello ruled as a boss of Luciano's family was a relatively peaceful one. After Genovese fled to Italy in fear of prosecution, Costello basically had the whole operation under his control, and he expanded the crime family's operations.
After Luciano was deported to Italy in 1946 and Genovese decided to return to the States, Costello had trouble. Genovese wanted to become boss, and Costello acceded to let him be the top boss in order to avoid an all out war. Genovese seemed to be pleased at the way things had changed during Costello's period as boss, and he was very impressed with the fact Costello was good friends with Albert Anastasia. Things started to change when the Kefauver hearings came. Mafia leaders from across the States were called for interviews to be investigated, and Costello became the United States' best known gangster of the time. The hearings were called by the Kefauver commission, which wanted to investigate organized crime in the States.
Genovese by 1951 wanted to get rid of Costello. But Costello was able to get away because he was sentenced to 18 months of jail, accused of contempt of the Senate. He started serving that sentence in August of 1952, but was released after only 14 months, in October of 1953.
In 1954, he was accused of tax evasion and sentenced to five years in jail, but he didn't have to serve any time from that sentence. In 1956, he was once again convicted, and he was sent to prison that time. But he prevailed on appeal and was out the next year.
Costello suffered a murder attempt soon after getting out, when, one night, he was walking to the elevator in order to go up to his house, and was shot in the head by hitman Vincent Gigante, who supposedly warned him by shouting "Frank, this is for you!!" before taking his shot. Costello turned around, and ducked when he saw the fire come towards him. Because of that defensive reaction, he was able to survive the attack. Gigante left him for dead and ran away, but the bullet had really just grazed his head, tearing thru his right ear and slightly touching his neck. Genovese then appointed himself as boss, even though his attempt on Costello had failed.
Some time after that, Costello made it clear to Genovese that he wanted to be a Mafia boss no more and wanted peace. Genovese agreed to leave Costello alone, but he made Costello give up his gambling connections everywhere and go back to just being a soldier for the organization. Eventually Genovese made Costello agree to leave and never get involved in underworld business anymore.
Costello led a relatively peaceful and quiet life his final years, and in 1973, he died of a heart attack at a Manhattan hospital.