Zvečer pred 16. decembrom 1985 je Bilotti peljal Castellana s črnim lincolnom iz Brooklyna na Manhattan v restavracijo Sparks na vogalu 3. avenije in 46. ulice. Ko so pred restavracijo stopili iz avtomobila, sta k njim pristopila moška: Castellana je zadelo šest strelov v glavo in prsi, padel je na hrbet in iz roke mu je padla cigara. Potem ko je padel, ga je morilec za vsak primer še enkrat ustrelil v glavo. Tudi Bilotti je prerešetan padel na tla. Morilca sta vstopila v avtomobil, ki ju je čakal, in zapodili so se po 3. aveniji proti jugu. S kraja dogodka je hitro odpeljalo še nekaj parkiranih avtomobilov. V enem od njih je bil Gotti, ki je umor ukazal, organiziral in nadzoroval. S tem umorom je Gotti postal boss "družine" Gambino in "boss bossov". Kot najmočnejši ameriški mafijec je John Gotti postal predmet zanimanja ameriških raziskovalcev. Mlada državna tožilka Diane Giacalone, ki je otroštvo preživela v istem predelu Queensa kot Gotti, je začela raziskovati njegove zločine, odločna, da ga pripelje pred sodišče in spravi v zapor. Na prvem sojenju leta 1986 ga je obtožila, da je z nekim pajdašem fizično napadel Romuala Piecyka, ki je bil najprej pripravljen obtožiti Gottija, ko se je sojenje približevalo, pa je naenkrat "pozabil", kdo ga je napadel in Gotti je bil osvobojen. Neuspešna je bila tudi naslednja obtožnica zaradi terjanja denarja od trgovcev in organiziranja ilegalnih iger na srečo. To drugo sojenje jeseni 1986 je izzvalo veliko zanimanje medijev. Gotti je tudi na sodišču želel delovati kot moderen, uspešen poslovnež in se je na sojenje vsakič pripeljal v najmodernejšem mercedesu, oblečen v luksuzne obleke, vredne dva tisoč dolarjev. Hkrati se je v drugi sodni dvorani odvijal proces proti ostalim štirim šefom newyorških družin: Anthonyju Salernu, šefu družine Genovese, Anthonyju Corallu, šefu družine Lucchese, Philipu Rastellu, šefu družine Bonanno, in Carminu Persicu, šefu družine Colombo. Obsojeni so bili na skupno več kot sto let zapora. Predvidevalo se je, da bo obsojen tudi Gotti, toda v začetku leta 1987 je bil Gotti oproščen zaradi pomanjkanja dokazov. Dobil je nov vzdevek Teflon Don (Nelepljivi Don), zaradi pomanjkanja dokazov pa je bil potem oproščen še dvakrat. Februarja 1990 so ga obtožili, da je organiziral poskus umora nekega sindikalnega aktivista, a je ta pred sodiščem svojo zgodbo spremenil. V drugi polovici leta 1990 so ga ponovno aretirali in tožilstvo se je na sojenje, ki se je začelo šele na začetku leta 1992, zelo dobro pripravilo. Ključni trenutek sojenja je bil, ko so tožilci pred poroto privedli enega Gottijevih najbližjih sodelavcev, ki je pristal na sodelovanje s tožilci in se je odločil izdati vse, kar ve. To je bil mafijski morilec