Razem z grupą Luciany organizowali napady, kradzieże, wymuszenia oraz przemyt alkoholu, na który nałożono prohibicję w latach dwudziestych XX wieku.
Na przełomie lat dwudziestych i trzydziestych doszło do poważnego konfliktu między zwierzchnikiem Luciany, Giuseppem Masserią a Salvatorem Maranzaną, gangsterem, który przybył w 1925 roku do Stanów z polecenia mafiosów sycylijskich. Siłą rzeczy Gambino został włączony w wojnę dwóch frakcji mafijnych, której korzenie sięgały jeszcze Sycylii oraz Neapolu. Konflikt okazał się być bardzo wyniszczającym starciem dla obu stron, w wyniku którego zginęło wiele osób. Młodzi mafiozi doprowadzili do śmierci Masserii, który został zastrzelony 15 kwietnia 1931 roku podczas obiadu w jednej z nowojorskich restauracji. Maranzano wygrał więc wojnę i został mianowany capo di tutti capi, „szefem wszystkich szefów”. Jego kariera nie trwała długo, gdyż 10 września tego samego roku został zamordowany w swoim biurze na Manhattanie. Za zabójstwem stał Luciano i spółka, którzy po wyeliminowaniu obu szefów, przejęli kontrolę nad mafią w USA, dając w ten sposób początek amerykańskiej Cosa Nostrze. Gambino pozostał w ekipie Luciany, dzięki czemu zyskał znaczącą pozycję oraz doskonałe perspektywy na przyszłość.