Frank został członkiem gangu kontrolującego hazard, wymuszenia, napady i narkotyki na Manhattanie i Bronksie.
W czasie pracy dla Terranovy Castiglia poznał i zaprzyjaźnił się z Salvatorem Lucania, znanym później jako Charles „Lucky” Luciano, sycylijskim liderem gangu Manhattan’s Lower East Side. Razem z innymi Włochami Vito Genovese i Gaetano Lucchese oraz z żydowskimi wspólnikami Meyerem Lanskim i Benjaminem „Bugsy” Siegelem, gang przeprowadzał rozboje, kradzieże i wymuszenia oraz kontrolował hazard i handel narkotykami. Przymierze Lucania-Castiglia-Lansky zaczęło prosperować, a w czasie wprowadzenia prohibicji na alkohol w 1919 roku, gdy zajęli się nielegalną sprzedażą alkoholu. Ich sukcesem zainteresowali się prominentni żydowscy i irlandzcy bossowie nowojorskiego podziemia. W 1924 roku Castiglia i jego włoscy towarzysze zaczęli pracować dla jednej z największych irlandzkich rodzin mafijnych w Nowym Jorku. Ten krok skłonił Castiglię do zmiany nazwiska na bardziej irlandzko brzmiące – Costello.
Po uwięzieniu jednego z bossów mafii Costello próbował sam zostać bossem. Nie udało mu się to ponieważ Irlandczycy uważali, że to oni powinni kierować swoimi interesami.