Рагано характеризовал Луккезе как самого надежного союзника Траффиканте в нью-йоркских семьях. Флоридский босс особенно восхищался связями Луккезе с коррумпированными правительственными чиновниками. «У этого парня есть связи повсюду в Нью-Йорке, — говорил Траффиканте Рагано с оттенком зависти. — У него в кармане политики и судьи».

В политической сфере Луккезе поддерживал тесный союз с Фрэнком Костелло и, как и премьер-министр, стал силовым посредником в нью-йоркской машине Демократической партии и при назначении коррумпированных судей, помощников окружных прокуроров и городских чиновников. Но в отличие от Костелло, интересы Луккезе оставались скрытыми и никогда не привлекали внимания общественности. Кроме того, Луккезе сотрудничал с чиновниками-республиканцами и расширил свой круг до радикального крыла политики. Он успешно лоббировал Вито Маркантонио, конгрессмена, представлявшего его старый район Ист-Гарлем, единственного члена Палаты представителей, неоднократно избранного левацкой Американской рабочей партией, чтобы тот выдвинул кандидатуру его сына для поступления в Вест-Пойнт. (Один из сыновей Мейера Лански также был выпускником Вест-Пойнта.) Загородный дом Луккезе находился далеко от железнодорожных квартир Восточного Гарлема, но мафия все равно влияла на голоса избирателей в этом районе, где в то время было много итальянцев.

Незаметное влияние Томми Луккезе на законодателей и политиков было продемонстрировано, когда в 1943 году он был натурализован в качестве гражданина по частному законопроекту, одобренному Конгрессом. Примерно в то же время несколько законодателей убедили Совет по условно-досрочному освобождению штата Нью-Йорк выдать Луккезе «Сертификат хорошего поведения», аннулировав его аресты и приговоры, вынесенные в 1920-х годах за кражу автомобилей и букмекерство.

В 1945 году, вероятно, в результате закулисной сделки с Фрэнком Костелло и Таммани-холлом, Луккезе выбрал второстепенного клубного политика и соратника американца сицилийского происхождения Винсента Р. Импеллиттери в качестве соратника О'Дуайера по Демократическому билету. О'Дуайер был избран мэром, а Импеллиттери, чей единственный опыт работы заключался в работе клерком судьи-демократа, стал председателем городского совета, что было в основном церемониальной должностью. Когда в 1950 году О'Дуайер ушел в отставку, Импеллиттери («Импи» в заголовках таблоидов) сменил его на посту исполняющего обязанности мэра. Однако лидеры Таммани считали Импеллиттери слишком некомпетентным, слишком невнятным и слишком легковесным даже по их скромным меркам. Они поддержали судью Фердинанда Пекору на выборах мэра в 1951 году.

Импеллиттери, привыкший к помпезности, власти и привилегиям мэрии, отказался выбыть из гонки и баллотировался как единственный кандидат от недавно созданной «Партии опыта». В результате выборов мафия оказалась в незавидном положении: Луккезе тайно поддерживал Импи, а Костелло — Пекору.

Поскольку откровения, сделанные на слушаниях в Кефовере, были еще свежи в памяти избирателей, Импеллиттери направил свою кампанию против Таммани-Холла, мафии и Костелло — той самой группы, которая подняла его от клерка-юриста до мэра. В каждой своей речи он заявлял: «Если Пекора будет избран, Фрэнк Костелло станет вашим мэром». С помощью ловкой кампании по связям с общественностью Импеллиттери одержал поразительную победу, став единственным кандидатом от независимой партии, когда-либо избранным мэром Нью-Йорка. Вскоре после вступления в должность Импеллиттери был замечен в ресторане с Луккезе и бывшим федеральным прокурором. На вопросы репортеров мэр невинно заявил, что едва знаком с Луккезе и что гангстер был представлен ему как производитель одежды. Оказавшись неудачником, Импеллиттери был смещен с поста в 1954 году, после одного сокращенного срока. В том конкурсе на пост мэра все обернулось против него: реформаторы обвинили его в связях с организованной преступностью. Политические и мафиозные друзья Импеллиттери не оставили его. Они помогли ему занять удобную судейскую должность. Однако с поражением Импи бесценный канал связи мафии с мэрией был, по сути, перерезан.

После недолгого тюремного заключения и слушаний в комитете Кефовера Фрэнк Костелло весной 1957 года уверенно занимался своими обычными делами. Отказавшись от телохранителей и пуленепробиваемых лимузинов, 66-летний крестный отец встречался со своими подельниками-мафиози в ресторанах и разъезжал по Манхэттену на такси, как любой обычный бизнесмен.

2 мая 1957 года у Костелло был поздний ужин с Энтони «Тони Бендером» Стролло, одним из его капо, в ресторане Chandler's, расположенном в театральном районе. Как обычно, он взял такси и вернулся в свою роскошную квартиру на Централ-Парк-Уэст. Когда Костелло шел к лифту, мужчина в темной фетровой шляпе пронесся мимо швейцара и крикнул: «Это тебе, Фрэнк». Повернувшись, Костелло услышал звук, похожий на хлопушку, и пуля пробила ему правую часть лба, повалив на землю. Стрелок скрылся на поджидавшем его черном «Кадиллаке».

Получивший легкое ранение и перевязанную голову в приемном покое больницы, хмурый Костелло не сообщил полиции никакой информации о том, что в него стреляли почти в упор. «Я ничего не видел», — сказал он детективам. При обыске его карманов был обнаружен интересный предмет: листок бумаги с пометкой «Валовый выигрыш в казино на 4-27-57 — 651 284 доллара». Эта цифра, как позже выяснили детективы, полностью совпадала с суммой валового выигрыша, полученного в тот день в новом казино Лас-Вегаса «Тропикана», в котором Костелло был главным тайным партнером.

Хотя Костелло признался, что не знает, зачем кому-то понадобилось его убивать, у детективов появилась сильная версия, что наиболее вероятный мотив для заключения контракта с премьер-министром был у Вито Дженовезе. Выписавшись из больницы, Костелло сообщил полиции, что не опасается за свою жизнь и продолжит свой обычный обход без единого телохранителя. Однако полицейское начальство поручило двум детективам присматривать за раненым боссом. Когда детективы появились в тамбуре перед его квартирой, утонченный Костелло настоял на том, чтобы они зашли позавтракать вместе с ним и его женой. Один из следователей был итало-американцем, и он рассказал коллеге-детективу Ральфу Салерно, что невозмутимый Костелло поспорил с ним. «Что такой итальянский парень, как ты, делает со всеми этими ирландскими копами? — спросил Костелло. — Они платят тебе арахис. Пойдем с нами. Мы платим бананы, и они приходят большими гроздьями».

В первый же день своего задания люди в штатском последовали за такси Костелло к отелю «Уолдорф-Астория» на машине без опознавательных знаков. Он почти ежедневно ходил туда на маникюр, стрижку и массаж, а также на конференции в бар и ресторан отеля. Раздраженный перспективой постоянно оставаться в тени, Костелло предложил компромисс. «Давайте будем джентльменами, — сказал он детективам. — Я иду к своей девушке и не хочу, чтобы вы стояли за мной». Посоветовав детективам, что он легко может дать 100 долларов таксисту, чтобы тот потряс их, выставив их в дурном свете, он пообещал вернуться в «Уолдорф» примерно через два с половиной часа, и тогда они смогут возобновить наблюдение за ним. В течение следующих нескольких дней, пока полиция не отменила слежку, «джентльменское соглашение» существовало между детективами и Костелло всякий раз, когда у него было назначено свидание.

Прокурор Манхэттена Фрэнк Хоган не был столь любезен, как полиция. Он вызвал Костелло в суд присяжных, требуя ответов о стрельбе и выигрыше в казино в размере 651 284 долларов. На этот раз, ссылаясь на свою Пятую поправку, Костелло отказался говорить о покушении на его жизнь и о клочке бумаги, найденном в его кармане. В итоге, прежде чем кого-то арестовали за то, что он продырявил себе лоб пулей, пострадавший Костелло отсидел шестьдесят дней в «рабочем доме», муниципальной тюрьме, за неуважение к суду.