フランク・コステロ
若年期
カラブリア州カッサーノ・アッロ・イオーニオ郊外のラウロポリ出身。貧農の父ドン・ルイージ、母マリアの6番目の子として生まれた。1895年10月4日に母親やその姉妹とともに渡米し、ニューヨークのイースト・ハーレム108丁目に定住した。親は小さな雑貨屋を営んだ。公立学校に通うが、13歳でやめた。父の勧めでピアノ工場で働くが、12時間の厳しい労働の上、給料も安かったため、1年ほどでやめた。1905年14歳の時、船の甲板員に雇われ 、アメリカと中南米を往復した。1908年と1912年に、武装強盗の共犯で捕まった。1914年9月23日に知人の妹のロレッタ（通称ボビー）というドイツ系ユダヤ人と結婚した。1915年4月、拳銃の不法所持で捕まり、強盗逮捕歴2回を重く見られ、懲役1年の実刑となった（10ヵ月で出所）。以来銃の携帯を控えるようになった。
1919年後半、ヘンリー・ホロウィッツという男と雑貨会社（ホロウィッツ・ノヴェルティ）を設立し、表向きは日用品の販売だったが、当時流行した非合法のパンチボード賭博の道具やその景品のキューピー人形を売って回った。酒場などに置かれ、当たった景品をバーテンに持っていくと、こっそり換金できた。出所してから禁酒法が始まるまでその会社にいたとコステロは後年振り返ったが、会社設立は禁酒法施行の5か月前で、その前の3年半、何をやっていたか不明である。1919年、同じハーレムのヴィンセント・ラオ（後のルッケーゼ一家幹部）らが泥棒で捕まった時一緒にいたとされる。
禁酒法時代
1921年頃、ユダヤ系ギャングのアーノルド・ロススタインの資金援助を得て、兄エディと共にマンハッタンのウェストサイドの波止場を拠点に酒の密輸を始めた。当時アメリカ政府が英国政府に圧力をかけ、密輸の一大拠点だったバハマから密輸ギャングを駆逐していた。ロングアイランド沖3マイル以上は国際海域で取締りの対象外だった為、密輸ギャングがアメリカ・カナダの国境沿いに大挙して押し寄せた。コステロは、ニューファンドランド沖のサンピエール島で酒を仕入れ、ニューヨーク沖のラム・ロウ（酒屋通り）まで運び、そこからロングアイランドなど米国本土沿岸の港に無数の小船に積み替えて運んだ。サンピエール島はギャングに好都合なことにフランス領で、1921年末までに島はゴールドラッシュ化した。
アメリカ沿岸警備隊（コーストガード）の船は災害救助用に造られた14ノットの低速船で、重武装した24ノットの密輸ボートに太刀打ちできず、コステロらは堂々と酒を運ぶことができた。1ケース8ドルで仕入れた酒がアメリカで120ドルで売れ、更にこれを原酒と水で薄めたブレンド酒に1：3の割合で分けて詰め替えると原価8ドルが400ドルになった。カナダの醸造業者サミュエル・ブロンフマンらから酒を買ったが、1922年、サンピエール島で知り合ったアイルランド系の同業者ビル・ドワイヤーと酒の仕入れで提携し、買い手同士団結して交渉に当たり、やがて組織を合体した。人手が足りないとウェストサイドの酒場に入り浸るごろつきを雇い入れてサンピエール島に送り込み、酒の希釈・瓶の詰め替え作業を数百人体制で行った。税関役人、密輸捜査官、警官らを買収して運搬時のガード役や見張り番に雇い、コーストガードのパトロール員は接待して日々の活動情報を入手した。海洋より内陸輸送の方が危険で、酒のハイジャックが横行した。アイルランド系ギャングのオウニー・マドゥンを引き入れて武装を強化し、マドゥンはそのまま組織のパートナーとなった。
コーストガードは海軍から駆逐艦を借り上げ、各船に長距離ライフルと機関銃を配し、密輸船団に対抗できる高速船を建造し始めた。1924年春、ラム・ロウでコーストガード.と密輸船の激烈な戦いになった。コステロは、公開された政府の新造船のスペックを船の建造業者に送り、別途調達したパワフルな飛行機エンジンを搭載した高速船を造らせ、それに高周波無線と機関銃の砲座を取り付けた。岸側と船側に高周波無線ステーションを設け、ミッドタウンのレキシントン・アヴェニューのコステロの本部に直結した。摘発の動きがあるとコーストガードの内部情報により摘発を免れた。
物流部、賄賂部、護衛部、諜報部など、会社のような整然たる組織を持ち、ニューヨークで最も大きな密輸組織の1つと言われた。ロングアイランドのうらびれた浜辺からニューヨークの倉庫まで運ぶコンボイ軍団の護衛に雇った武装用心棒には、ランスキー＆バグジー・シーゲルのギャング団も含まれた。
1925年12月、コーストガード中枢へのドワイヤーの派手な接待攻勢が露見し、芋づる式に摘発された（賄賂を受けたコーストガード職員も逮捕）。ドワイヤーは組織の主犯と見なされたが、コステロは「酒の買い手」と見なされ、陪審を買収して無罪となった（ドワイヤーは実刑となり11か月で出所）。摘発後、ドワイヤーが密輸から手を引くと、彼の手下だったバニー・ヒギンズが頭角を現し、縄張り争いになった。海上取締り強化によりアルコール犯罪の主流が海上密輸から国内密造にシフトする中、コステロは密輸オペレーションを縮小し、賭博業にウェイトを移した。
酒の密輸を通じてドワイヤーやマドゥンなどアイルランド系、ジョー・マッセリア、ラッキー・ルチアーノやヴィト・ジェノヴェーゼらのイタリア系、ランスキー、シーゲル、アブナー・ツヴィルマン、ダッチ・シュルツ、ルイス・バカルターらユダヤ系ギャングと知り合った。1928年11月、ロススタインがポーカー仲間に銃で撃たれて死んだ時、コステロはロススタインに事業資金3万ドルを借りていた。「監視を始めた頃、彼の親しい仲間はユダヤ系かアイルランド系で、イタリア系といるのを見たことがなかった」（コステロを長年監視したニューヨーク市警刑事）とされたが、実際はルチアーノなどイタリア系とも付き合っていた。民主党の政治組織タマニー・ホールに人脈を広げ、ジミー・ウォーカーのニューヨーク市長選に協力して政治的な保護を受けた。1925年、本名カスティーリャでアメリカの国籍を取得した。アイルランド風のフランク・コステロと名前を使い分けていたが(密輸で捕まった時はコステロ)、1930年代以降コステロに一本化した。1927年、イタリアの故郷に凱旋帰国した。
スロットマシン
1920年代後半、禁酒法の終焉を見越してフィル・カステルとスロットマシン事業を始めた。1929年までにスロットマシンメーカー大手ミルズ・ノヴェルティ（本社シカゴ）と販売契約を結び、1931年までにニューヨーク市エリアの供給を独占した。トゥル・ミント・カンパニーを設立し、スロットの景品であるミント（飴玉）を販売した。スロットは一見ミントの自動販売機だったが、簡単な細工でミントの代わりに鉄玉を使った賭博マシンに変化した。換金は80～82％で払い戻しされた。ミントの販売機は合法とされ、警察は賭博行為の証拠をおさえない限り摘発できなかった。
スピークイージー、ナイトクラブ、ドラッグストア、煙草屋、駄菓子屋などに幅広く置かれ、店オーナーに上がりの40％を払った。1931年時点で、コステロは5186個のマシンを所有した。トゥル・ミントの事務所に14人の電話オペレーターが常駐し、壊れたマシンの修繕や取替に機械技師を派遣した。自販機も抱き合わせで営業し、1日あたり粗利益10万ドルを稼ぎ出した。ニューヨークを行政区や警察管区ごとに区切って販売代理店を設け、ブロンクスはダッチ・シュルツ、ハーレムはジョーイ・ラオ（シュルツ＝テラノヴァ連合）、ブルックリンはアンソニー・カルファノが販売権を得た。警察の嫌がらせで傘下の販売店がトラブルにあうこともあったが、大部分はタマニーコネクションや汚職警官のお蔭で守られた。
1934年1月、ニューヨーク市長になったフィオレロ・ラガーディアがスロットマシンの摘発に乗り出し、警官を動員して1000個を押収した。コステロ一味はすぐに4000個を保管庫に隠した。ラガーディアは使われてない昔の法律を引っ張り出してきて特定の訴追ができる特殊な司法権限を自らに与え、警察分署でスロットヒアリングを実施、その場でオペレーターらに刑を宣告した。マスコミを集めて船の甲板に上がりハンマーでスロットを叩き壊し、海に投げ込んだ。公文書上でしばしばコステロを能無し（BUM）呼ばわりした。ラガーディアの情熱的なスロット十字軍は、コステロが市長選挙で対立陣営を支援したことに端を発した。スロットの次に流行したピンボールマシンは同じ種類のギャンブルだったが、オペレーターがラガーディアの支援者だった為、大手を振って営業が行われた（違法クラップゲームは公然と許可した）。
五大ファミリー
1931年、ニューヨーク五大ファミリーが整理され、ルチアーノがマッセリアを継いでルチアーノ一家（現ジェノヴェーゼ一家）のボスになった時、相談役の地位に収まっていた。ウィリー・モレッティ、ジョー・アドニス、カルファノら一家内の支持基盤を固めた。五大ファミリーでは、マンガーノ一家（現ガンビーノ一家）の副ボス、アルバート・アナスタシアと強力なタッグを組んだ。アル・カポネ収監後のシカゴ・アウトフィットの上層部とも強い信頼関係を築いた。
1933年の禁酒法廃止後、多くのギャングは酒ビジネスから撤退したが、そのまま続けるギャングもいた。コステロもその1人で、1933年12月に合法の酒販売会社を作り、輸入スコッチウイスキーを卸売りした。1939年、このウイスキーメーカーの親会社（ロンドン）を買収し、アメリカにおける販売プロモーターの肩書で会社から年俸24000ドルを得た。個人的人脈を使ってアメリカのホテルやレストランへ商品の売り込みをかけるというのが仕事で、ホテル宿泊代やレストラン飲食代が経費で落ちた。
1930年代、最高級ホテルのウォルドルフ＝アストリアのスイートで暮らした。部屋が6つあり、執事やメイドが付いた。ルチアーノらもこのホテルに入居していた。後年、セントラルパークウエストの高級マンションに移り住んだ。
1930年代後半、トーマス・デューイ州特別検察官（マンハッタン地区担当）が手当たり次第にギャング犯罪を摘発し始め、多くのギャングがマンハッタンを追われた。ルチアーノや副ボスのヴィト・ジェノヴェーゼは潜伏し、アドニスはニュージャージーへ、カルファノはフロリダへ拠点を移したが、コステロは主力のスロット事業をルイジアナに移していた上、麻薬もナンバーズ賭博もやらず、デューイの捜査線から漏れた。実際はニューヨークで賭場の営業に関わったが（胴元に資金を提供するスポンサー）、フランク・エリクソンをフロントに立て、露見しなかった。合法投資家に転身したビル・ドワイヤーは国税局に目を付けられ、資産の多くを没収されたが、コステロは国税局の監視の網にも引っかからなかった。1936年、ルチアーノが逮捕され、ジェノヴェーゼがイタリアへ逃れると、自動的にルチアーノ一家のトップに立った（代理ボス）。
全米進出
1935年初め、スロットマシン事業をルイジアナ州元知事ヒューイ・ロングの裏保証を取り付けてニューオリンズに移し、カステルを派遣してこれを繁盛させた（最終的に合法化）。この時ルイジアナのボスのサム・カローラと取引をし、またニューオリンズで頭角を現したシチリア系のカルロス・マルセロとスロットの営業で提携した。
高級賭博クラブは、1933年にサラトガ・スプリングスでランスキーらとカジノ経営に参加して以来、全米各地に進出した。ランスキー、アドニスやエリクソンなどと複数のカジノ経営に相乗りした。アドニスやモレッティのニュージャージーの賭博クラブにシェアを持った。フロリダのマイアミは後のラスベガスの試金石になった。1945年、ルイジアナでランスキーやマルセロと共にビバリー・カントリー・クラブを開店した。
ランスキーやシーゲルらが主導したラスベガスの大型カジノ（フラミンゴ）の建設はコステロを筆頭にニューヨークマフィアが総出でバックアップした。フラミンゴは戦争直後の物資調達の遅延やシーゲルの資金流用もあって建設が難航したが、1947年に完成した。開店当初はつまずいたが、1948年後半、一転全米ブームを引き起こし、コステロは恩恵に与った。その後ラスベガスはカジノホテルの建設ラッシュが続き、コステロもサンズホテル（1952年）やトロピカーナ（1957年）などに経営参入した。
暗黒街の首相
1920年代からタマニー・ホールの政治ネットワークを通じて政界・司法界に影響力を広げていった。ジミー・ハインズやジミー・ケリー（ディサルヴィオ）、カーマイン・デサピオ、ユーゴ・ロジャースら多くの政治指導者と付き合いがあった。タマニーの中枢までコステロの権力は及び、州や市の判事・検事の人事を動かし、「暗黒街の首相」と言われた。「1942年にニューヨーク市政を完全に支配するに至った」（キーファーヴァー中間報告）とまで言われ、1940年代を通じてその権勢は頂点に達した。
1939年ユダヤ系の大物ルイス・バカルターがデューイに追われて潜伏した時、当局と折り合いをつけるために、政界人脈が豊富で、かつ自身が捕まる可能性の少ないコステロに頼ったと言われる。
1941年11月、マーダー・インクのエイブ・レルズが同僚の殺人関与を次々と証言した末、6人の警官に保護されたホテルの6階から墜落死したが、マーダー・インク副長だったアナスタシアに告発が及ぶのを恐れたコステロが事件の黒幕とされた。ブルックリン地区首席検事ウィリアム・オドワイヤーは1940年10月、レルズの証言を元にアナスタシアを殺人容疑で指名手配し、組合犯罪や未解決の失踪事件もアナスタシアの仕業として連日のようにアナスタシアをバッシングしていたが、レルズの死を境に捜査を打ち切った。レルズを警察の独房に置かずホテルの一室に置いたのはオドワイヤーで、ホテルの護衛を警官時代の旧友フランク・バルズに任せた。後年キーファーヴァー委員会に出頭したオドワイヤーは、アナスタシアの告発を打ち切った経緯を厳しく追及された。同じく委員会に呼ばれたバルズは、レルズ墜落死の真相を「自白」するよう殺人裁判の被告さながらに責め立てられた。
1945年、オドワイヤーはニューヨーク市長に当選したが、出馬する時にコステロに「許可」（選挙資金）をもらいに行ったことやマフィアの身内や仲間を公職に就かせていたこと、両者の連絡役を務めていたとする男の証言などがキーファーヴァー委員会で明らかにされた（オドワイヤーは1950年8月警察の汚職スキャンダルで市長を辞任）。
1943年8月、マンハッタン地区検事フランク・ホーガンが民主党攻撃の材料にコステロとトーマス・アウレリオ判事の電話の盗聴テープを公開し、政治スキャンダル化した。会話では、アウレリオがコステロにニューヨーク市の最高裁判事の指名を獲得した礼の言葉を述べ、コステロがそれを祝福し、続けてアウレリオが「あなたにしてもらったことに全力で報いる。一生ついていくつもりだ」 と忠誠の言葉を口にした。この盗聴テープは後年キーファーヴァー委員会で再び取り上げられた。
同じ頃コステロは、ルチアーノの釈放のためランスキーと共に政界工作に奔走した。最終的に、当時州知事になっていたデューイを動かし、1945年12月にルチアーノの特赦が決まった（外国人犯罪者処遇の通例に倣い、国外退去の形ではあったが）。デューイは後年、検事時代の活躍を買われてキーファーヴァー委員会に証言協力を求められたが、口実を設けて出席しなかった。その後、ランスキー傘下の会社の顧問になった。
FBIのジョン・エドガー・フーヴァー長官との付き合いは1920年代後半に始まり、2人とも競馬好きで一緒にレース見物に行った。コステロはフーヴァーの10ドル、20ドルというケチな賭けのため、インチキレースを仕組んだりしたという。1935年6月、コステロのニューヨークの賭博団の一員がマイマミで強盗を働いて捕まった時、コステロも逮捕され、FBIはコステロを調査したが、司法省の命令で動いただけで、2年後に告訴を取り下げた。フーヴァーはワシントンの本部からちょくちょくマンハッタンに来てコステロとセントラルパークで会っていたという（複数のFBIエージェントの言）。50年間FBIのトップに君臨したフーヴァーは、8人の大統領と17人の司法長官にマフィアの組織はアメリカに存在しないと言い続けた。
ハバナ会議
1946年2月、ルチアーノがイタリアに移送され、再入国が絶望的になると正式に一家のボスの座を継いだ。同じ頃、ジェノヴェーゼがイタリアから連れ戻され、昔の殺人で裁判にかけられていたが、1946年6月に釈放され、組織に復帰した。コステロはジェノヴェーゼの復帰を歓迎し、当座の資金として2万ドルを貸したが、ボスの座も副ボスの座も渡さなかった。ジェノヴェーゼは副ボスの座を剥ぎ取られたが、一家の幹部や全米のマフィアから支持されるコステロと表立って争わず、水面下で幹部の切り崩しにかかった。
1946年12月、アドニス、ランスキーらとキューバに全米のギャングを一堂に集め、イタリアに帰還したルチアーノを招いてハバナ会議を主催した。一家のテリトリーはニュージャージーやコネチカットまで及び、賭博・高利貸しから金融投資まで多岐のビジネスに進出した。コステロはファミリーの構成員に対し強い締め付けはせず、部下は自由に自分のビジネスをし、ファミリー全体が潤っていた。当局は、コステロが頻繁に会っている人物から上下関係を判断できず、従って犯罪組織での立場もわからなかった。ニューヨーク市警の知り得た情報は、賭博業を営み、店のオペレーターと付き合いが長いといった事だけだった。
1946年12月に一家のマイク・コッポラが麻薬で捕まった時、FBN（連邦麻薬捜査局）が、「ハーレム麻薬シンジケート」を背後から操っているのがコステロだと誌上で名指しして非難した。コステロは異例の記者会見を開いて全くの事実無根と反論し、「麻薬に関わる者は最低の人間である」と麻薬犯罪者への抗議声明文を読み上げた。この時のFBNは、コステロを「ニューヨークの5つの犯罪グループの中で最も大きいグループのボス」とした。
1949年1月、救世軍基金の慈善プログラムに参加した。裏社会の繋がりの噂が絶えなかった為イメージを改善しようと、自身のクラブ「コパコバーナ」で盛大な慈善パーティを開いた。費用は全部コステロ持ちで、市政の大物が多数招待されたこのパーティはマスコミにすっぱ抜かれ、政界とギャングの結びつきを象徴する出来事としてネガティブな注目を浴びた（エピソード参照）。このパーティにはジェノヴェーゼも招待された。
1949年11月、タイム誌の表紙を飾り、本人の意に反して全国の有名人になった。
キーファーヴァー委員会
1951年3月13日、上院の組織犯罪調査委員会（通称キーファーヴァー委員会）の公聴会に出頭し、各地の賭博業から過去の密輸、国籍取得手続まで厳しい質問を浴びた。公聴会は全国14都市で開かれ、出頭したマフィアの多くは黙秘権を行使したが、全国ツアーを締めくくるグランドフィナーレの舞台に真打ちのごとく登場したコステロは、黙秘権を使わずにアドリブで対応し、途中で勝手に退席するなど気ままに振る舞った。キーファーヴァーは大統領候補指名欲しさに公聴会をゴールデンタイムのテレビ中継に合わせ、議会侮辱罪をちらつかせて証言を迫ったが、コステロは言葉少なめにのらりくらりと追及をはぐらかした。
開始直前のコステロの要望で、テレビは顔を映さず、手だけを映したため、視聴者はその肉声（しゃがれ声）に釘付けとなった。コステロのかすれたような声は議員に「カモメの断末魔の鳴き声」と揶揄されたが、視聴者には「闇の支配者」のイメージを植え付けた。新聞は連日一面トップで報じ、国税局のＧメンに加え、新聞記者もコステロを追いかけるようになった。1952年4月、公聴会で勝手に退席したことで議会侮辱罪に問われ、18か月の禁固処分になった。
キーファーヴァー委員会はマフィア組織の解明はおろか組織の存在も判然としないまま幕を閉じたが、世間の反響は大きく、税務当局が本格捜査に入り、政界仲間がコステロと距離を置いた。
国税局はコステロの1946年～1949年の4年間の脱税立件を決め、2人の腕利き捜査官がコステロの良く行く店、銀行、証券会社などから金銭情報をかき集めた。コステロは事業、買い物、寄付金、賄賂を現金ベースで行い、賭博の上がりも現金で受け取った。ビジネスでも雑事でもフロントの仲間を立て、又は家族名で活動した。ロングアイランドの12部屋のサンズポイントの別荘は妻の名義だった。1950年代まで、全米各地の賭博クラブ、ロングアイランドの競馬場、ルイジアナのスロットマシン、ラスベガスのカジノ、不動産、株投資、石油利権、ジュークボックスなど多様な収入源を持ったが、トータルの収入は国税局でも把握困難だった。結局、国税局は支出の大きさから逆算するとコステロの申告収入はありえない（くらい少ない）という論法で裁判に持ち込んだ。1954年5月、脱税で懲役5年の有罪となり、1956年5月収監されたが、弁護士の入れ知恵で判決保留となり11か月で出所した。1958年、刑期確定で再び監獄行きとなり、1961年6月に出所した。
権力闘争
1951年4月、盟友のアルバート・アナスタシアをマンガーノ一家のボスに据えて味方陣営を固め、ジェノヴェーゼを牽制した。1951年10月4日、モレッティが梅毒の後遺症による精神障害を理由に粛清され、強力な仲間が一人消えた。
モレッティの死や当局のコステロ叩きはジェノヴェーゼに追い風となった。資金協力や便宜の提供を通じて各地の幹部を自陣に加えると共に、ルッケーゼ一家のボスのトーマス・ルッケーゼと連携し、ファミリー内外からコステロ包囲網を敷いた。1956年、一家の中核のアドニスが政府の国外追放手続開始によりイタリアに逃亡し、ロッコ・ペリグリーノらコステロ派の長老幹部2人が一線から身を退いた。
1957年5月2日夜、コステロは親しい業界人3人と外で食事した。23時前、家に電話の用事があるからと途中で退席し、タクシーでセントラルパークウェストの自宅マンションに帰った。玄関からロビーに差しかかった時、中折れ帽にスーツ姿の大男が背後に現れ、「これを食らえ、フランク」と叫びながら至近距離からコステロを撃った。コステロは顔を守ろうととっさに腕を上げたが頭に命中し、血が飛び散って崩れ落ちた。大男は玄関へダッシュし、玄関付近で鉢合わせしたドアマンを銃を振り回して威嚇しながら、黒いキャデラックに乗って逃げた。病院に担ぎ込まれたが、発砲は1発だけで側頭部の頭皮をかする軽傷で済んだ。
3か月後ドアマンの証言などからジェノヴェーゼの配下ヴィンセント・ジガンテが捕まり、翌年5月、殺人未遂で裁判にかけられた。証人として出席したコステロは警察に尋問された時と同じように、犯人を見ていないと証言し、ジガンテは無罪となった。
コステロはボスの座を降りることを決意した。1946年時点と正反対に大方の幹部はジェノヴェーゼ支持に回り、裁判対応に追われ、ボス稼業にうんざりしていた。襲撃後ほどなくジェノヴェーゼに和平のメッセージを送り、二度と自分を襲わないこと、個人的な賭博利権を保持することを条件にジェノヴェーゼに一家を譲り渡した。コステロ襲撃に怒ったアナスタシアは、コミッションの席上、ジェノヴェーゼと戦争の場合は中立を保つようボス達に訴えたが、ボス達は、抗争を始めるつもりなら断固反対すると警告し、抗争しないよう説得したという。同年10月25日、マンハッタンの理髪屋でアナスタシアは2人組のヒットマンに暗殺され、すぐにアナスタシアの副ボスのカルロ・ガンビーノがボスに取って代わった。ルッケーゼの支持の元ガンビーノにジェノヴェーゼが手を回した結果と信じられている。
同年11月、全米マフィアが集まったアパラチン会議は警察に捕捉され、多数のマフィアが森に逃げ込むなどして60人以上が拘束された。場所の選定はステファノ・マガディーノが行ったが、全米マフィアの前で権力の移譲を内外に示すという元々のアイデアは、一説に身の危険をまだ感じていたコステロの発案とされる。
ジェノヴェーゼは1958年7月に麻薬取締法違反で逮捕され、裁判の末15年刑の有罪となったが、コステロがガンビーノやルチアーノらと共謀し、若い麻薬犯を買収してジェノヴェーゼを罠に嵌めたとする説がある。証言した麻薬犯は全米各地で精力的に麻薬を運んでいたこと、ジェノヴェーゼ以外に多くのマフィアが同じ麻薬犯の証言で捕まっていることなどからコステロ謀略説を疑問視する見方もある。
晩年
ボス辞任後もガンビーノら大物ボスがアドバイスを請いにコステロの自宅を訪れるなど、隠然たる影響力を保持した。形式的にはソルジャーの身分に落ちたが、誰もソルジャーとは思わなかった。当局の追及は止まらず、弁護士との会議が日課となった。1959年国籍をはく奪され、国外退去命令が下ったが、控訴して連邦裁で命令を覆した。暇になると1930年代から足繁く通っていたホットスプリングスを訪問し、オウニー・マドゥンと旧交を温めた。
1973年、コステロは心臓発作を起こして運び込まれたマンハッタン島の病院で死亡した。彼が死亡したときニューヨーク・タイムズは1ページを使い報じた。
人物像
武装ギャング時代は武器を手にしたが、富豪になってから暴力を忌避する傾向が強まり、平和派を任じた。暴力に訴えれば、「自分の世界が安全になるどころか逆にますます危険になる」と言った。用心棒も付けなかった。「自分の命が狙われた場合、用心棒は真っ先に買収の対象になる」。「銃や爆弾に訴えるより政治家を手なずける方が収穫が大きい」、「まじめに努力すれば平和的解決を図れないことはほとんどない」とも言った。意見対立を全会一致に持っていくことを好み、争いはストリートでなく会議で解決した（「コステロの手にかかれば何でも平和に事が運ぶ」ジョゼフ・ヴァラキ）。立ち振る舞いはギャングというよりビジネスマンで、静かに落ち着いて話した。一方で犯罪組織のボスとして、レルズの口封じやアナスタシアのボス殺しの容認など殺人沙汰に何度か関わった。ストリートギャングの時代から邪魔なライバルが現れた時は兄エドワードが汚れ役を引き受け、弟フランクのシャドーのように行動したとも言われた。
血縁・地縁の観念が薄く、多国籍社会に順応した。出自によって徒党を組む1900年代の閉鎖的なイタリアコミュニティのディープスポットに育ちながらアイルランド系やユダヤ系と平気で付き合っていた。イタリアの貧村出で1日14時間働いても報われない両親の運命を引きずることに劣等感を感じ、名前を変えたという。コステロの伝記作家の多くが、1950年代にうつ病や不眠の症状を持ち、精神科医に相談していたと指摘している。
弁護士、銀行家、実業家、賭博屋、組合幹部、クラブ芸人、コラムニスト、俳優、映画製作者、新聞記者まで交際範囲は広く、柔和な物腰、独特の親しみやすさ、義理堅さで人を惹きつけたと言われる。ジガンテに銃撃された晩に会っていたのは自販機実業家、出版社社長、モデル業経営者らだった。全国のマフィアからはカリスマ視された。「温厚で人当たりが良く、外交家だった」（ジョゼフ・ボナンノ）。「ナイスガイだった。傲慢なほど巨大な自尊心を持っていたが、人にその部分を見せなかった」（ヴィンセント・アロ）。「コステロのような人間になりたくて彼の仕草をよく観察した」（サム・ジアンカーナ）。「彼に比肩できる人間など世の中にいない」（ミッキー・コーエン）。