Уход Дженовезе устранил внутреннюю враждебность к правлению Костелло со стороны других группировок семьи и утихомирил недовольство его большой долей семейных богатств от азартных игр, ростовщичества, вымогательства в Гармент-центре, а также обычных краж и угонов. Хорошие времена позволили Костелло закрепиться в легальном бизнесе, используя родственников как ширму для инвестиций в импорт спиртного, недвижимость и нефтяные компании.

Безусловно, самой опасной деятельностью Костелло было его тонкое проникновение в важные правительственные учреждения через влияние в Демократической партии города. Он был теневым маклером, который подрывал справедливость в судах и подкупал крупных чиновников, чтобы защитить мафиози и их рэкет. Пользуясь связями Лучано с политиками-демократами, Костелло использовал явные взятки и тайные пожертвования для установления беспрецедентного криминального контроля над Таммани-холлом.

С 1789 года Таммани-холл (или его официальное название — Исполнительный комитет Демократического комитета округа Нью-Йорк) был прототипом политической машины большого города к 1930-м годам. Название «Таммани-холл» стало синонимом фальсификации выборов, заключения муниципальных контрактов и раздачи патронажных должностей. За исключением редких и недолгих побед реформаторов, объединившихся с Республиканской партией для избрания независимого мэра, Таммани доминировал в городском правительстве более ста лет.

Уильям Марси Твид (Босс Твид), председатель Таммани в 1850-х и 1860-х годах, стал непревзойденным символом коррупции. Его самым возмутительным грабежом стало строительство здания суда за мэрией, которое должно было обойтись в 250 000 долларов. Под руководством Твида и его липкими пальцами цена взлетела до 12 миллионов долларов.

За свои излишества Твид в конце концов угодил в тюрьму, где и умер в 1878 году, но его скандалы не смогли положить конец влиянию Таммани. Он был последним протестантским главой Таммани, и его кончина привела к захвату власти чередой ирландско-американских политиков, которые были у руля на момент прихода Костелло.

Избрание Фиорелло ЛаГуардиа в 1933 году и его разгром «Таммани» неожиданно сделали политиков демократической машины более подвластными деньгам мафии, чем раньше. Под благосклонным управлением мэра-плейбоя Джимми Уокера с 1926 по 1933 год Таммани занимала тысячи муниципальных должностей и получала откаты от тех, кто занимал эти должности. ЛаГуардиа лишил Таммани покровительства, огромного количества должностей на государственной службе и возможности получать взятки, заключая муниципальные контракты. Лишившись нормального притока средств для обеспечения выборов на десятки жизненно важных городских должностей, включая должности судей и окружных прокуроров, Таммани обратилась к Фрэнку Костелло. Босс мафии с радостью открыл денежные шлюзы и, в свою очередь, стал фактическим главой Таммани-холла.

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

Пока не появился Костелло, Демократическая партия города находилась в основном в руках ирландских прихлебателей. Босс мафии решил, что настало время ввести в иерархию Таммани больше итало-американских районных лидеров, многие из которых находились на его содержании, и он это сделал. В результате изменений лидер мафии возглавил самое важное отделение Демократической партии в городе, получив право выдвигать кандидатов на самые высокие выборные должности. Томас Кесснер, биограф ЛаГуардиа, считает, что Костелло перевернул отношения, существовавшие между мафией и лидерами демократов. «В период своего расцвета Таммани продавала защиту организованной преступности, но к 1940-м годам гангстер Фрэнк Костелло стал заправлять всем, и до его ухода Таммани говорила с итальянским акцентом», — пишет Кесснер.

Другие боссы мафии стали обязаны Костелло за то, что он оказывал влияние на них, когда их солдатам и подельникам требовалась услуга от судьи, прокурора или хорошо поставленного городского чиновника. Способность Костелло дергать за политические и судебные ниточки повышала его авторитет в мафиозной комиссии и укрепляла его позиции на переговорах с другими боссами. Среди мафиози его политическая смекалка принесла ему гордое прозвище «премьер-министр».

Судьи, важные политики, конгрессмены, писатели, а также представители нью-йоркского общества и кафе без стеснения посещали званые вечера, которые Костелло часто устраивал в своем пентхаусе в Majestic Apartments с видом на Центральный парк. Со вкусом оформленные в стиле арт-деко, единственными показными нотами в квартире были позолоченное пианино и несколько игровых автоматов. Приветливый Костелло не пытался скрыть своего увлечения азартными играми, призывая своих гостей попробовать сыграть в слоты. Неизменно каждый игрок выигрывал небольшой джекпот из звонких монет. Когда один из гостей попытался вернуть четвертаки, Костелло напутствовал его: «Ты что, думаешь, я сопляк? В моем доме никто не проигрывает».

Костелло успешно маскировал свои политические мускулы и криминальное прошлое от общественности до 1943 года, когда он был поставлен в тупик законным прослушиванием его домашнего телефона, установленным рэкетирами, работавшими на Фрэнка С. Хогана, окружного прокурора Манхэттена, сменившего Тома Дьюи. Расследование не смогло уличить Костелло ни в одном обвинении в рэкете, но прослушка застала его за неприкрытыми разговорами о его участии в избирательных кампаниях. Разговор с Томасом Аурелио, который только что получил от Таммани-Холла кандидатуру на должность судьи Верховного суда штата, наглядно продемонстрировал умение Костелло надевать судейские мантии на услужливых кандидатов.

«Доброе утро, Франческо, как дела, и спасибо за все», — сказал Аурелио в качестве вступительного слова.

«Поздравляю, — ответил Костелло. — Все прошло идеально. Когда я говорю тебе, что дело сделано, можешь не сомневаться».

«А сейчас, — продолжил благодарный Аурелио, — я хочу заверить вас в своей преданности за все, что вы сделали. Она нерушима».

На слушаниях, посвященных выдвижению кандидата, Костелло с готовностью признался, что заручился благословением Таммани для Аурелио, что обеспечило его избрание. Невозмутимый Костелло признал, что именно он поставил на пост нынешнего лидера Таммани-холла Майкла Кеннеди, убедив четырех руководителей округов поддержать его. У Костелло было простое объяснение, почему руководители округов последовали его совету: они были «старыми друзьями».

Прокурор опубликовал телефонные записи в прессе, пытаясь сорвать судейство Аурелио. Тем не менее, при поддержке Таммани Аурелио был избран на четырнадцатилетний срок. Разоблачения закулисных политических сил Костелло принесли ему широкую известность, но не смогли ослабить его хватку в Таммани-холле.

Спустя годы откровения о встрече Костелло с Уильямом О'Двайером показали, как его власть распространилась на мэрию, когда демократы вернули себе пост мэра города в 1946 году. Бывший полицейский, адвокат и судья, демократ Билл О'Двайер был избран в 1940 году окружным прокурором Бруклина. В следующем году, как кандидат от демократов, он потерпел поражение на выборах мэра от Фиорелло ЛаГуардиа, который получил третий срок. Во время Второй мировой войны О'Двайер, теперь уже бригадный генерал армии, присутствовал на коктейльной вечеринке в пентхаусе Костелло в декабре 1942 года. Там же присутствовали три высших руководителя Таммани-Холла, и свидетели видели, как О'Двайер и Костелло долго беседовали в углу.

Невозможно представить, чтобы О'Двайер, будучи окружным прокурором и опытным политиком, не знал о криминальном авторитете Костелло. Политические инсайдеры считают, что О'Двайер, скорее всего, смотрел в будущее и добивался доброй воли Костелло и его одобрения для выдвижения на пост мэра от демократов в 1945 году. Он заручился поддержкой Таммани и был избран.