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

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

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

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

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

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

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

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

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

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

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

Дважды избранный мэром в 1940-х годах, О'Двайер признал, что после ухода с поста был обязан Костелло политическими услугами. По признанию О'Двайера, часть долга была погашена назначением друзей Костелло и других мафиози на важные муниципальные должности, в том числе комиссара пожарного департамента и второго по значимости чиновника в городском юридическом отделе. «Есть вещи, которые нужно делать политически, если хочешь сотрудничества», — загадочно ответил О'Двайер, когда его спросили о назначениях и отношениях с Костелло. Суть признания О'Двайера была очевидна: мафия десятилетиями была невидимой силой в политическом управлении крупнейшим городом Америки.

В редких интервью, которые давал Фрэнк Костелло, он никогда не признавался в причастности к мафии или в попытках коррумпировать правительство Нью-Йорка. Но было очевидно, что он жаждал такого же признания в утонченном высшем свете, какого добился в преступном мире. «Других детей воспитывают хорошо, отправляют в Гарвард и Йель, — говорил он, сетуя на свое скудное образование и уличный говор «дэс и дос». — А я? Я был воспитан как гриб».

В поисках внутреннего покоя, находясь между преступными группировками и уважаемым обществом, Костелло обратился к психоаналитику. Его аналитик предположил, что успешный мафиози стыдится своего прошлого, и порекомендовал ему бросить своих старых приятелей и завести новые отношения, проводя больше времени с культурными друзьями. Это было невозможное решение для босса боргаты, и Костелло бросил аналитика вместо гангстеров.

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