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

Амбиции Дженовезе не могли быть так просто отвергнуты Костелло. Он руководил одной из самых жестких команд в семье; его команда была главными киллерами Лучано. Взгляд темных глаз Дженовезе из-под кустистых бровей пугал самого смелого мафиози.

Дженовезе был на шесть лет моложе Костелло, он эмигрировал подростком из Росиглино, городка неподалеку от Неаполя, не получил достаточного образования, сносно говорил по-английски и устроил свою штаб-квартиру в районе Маленькая Италия на Манхэттене. Несмотря на репутацию вора, бандита и убийцы, грузный Дженовезе был арестован лишь однажды, когда ему было двадцать лет, по обвинению в хранении оружия, и отсидел в тюрьме шестьдесят дней. Его склонность решать проблемы — даже романтические — с помощью насилия стала достоянием мафии. Первая жена Вито умерла в 1931 году от туберкулеза, и он влюбился в замужнюю кузину, Анну Вернитико. Соратники считали, что Вито задушил ее мужа, чтобы тот мог жениться на ней.

Когда Костелло сменил Лучано, Дженовезе занялся наркотиками и был главным наркоторговцем семьи. Однако дело об убийстве избавило Костелло от беспокойства по поводу ревности Дженовезе. В 1937 году Вито был замешан в убийстве партнера, который тремя годами ранее помог ему в мошенничестве. Убийство произошло после того, как партнер имел наглость пожаловаться на то, что не получил свою долю награбленного. Узнав, что у прокуроров есть свидетель, готовый дать против него показания, Дженовезе бежал в Италию. Мальчик-иммигрант без гроша в кармане вернулся на родину в комфортных условиях, по слухам, с 750 000 долларов наличными. Кроме того, Анна Дженовезе часто навещала Вито в качестве курьера, каждый раз перевозя от 50 000 до 100 000 долларов наличными от брата Дженовезе, Майкла, который следил за рэкетирскими интересами Вито в Соединенных Штатах.

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

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

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

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

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

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

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

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