Несмотря на приличный IQ в 110 баллов, Готти был невнимательным учеником, а его школьные записи пестрели жалобами на то, что он не подчинялся учителям и нападал на учеников. Формальное обучение закончилось в шестнадцать лет, когда услужливые родители позволили ему бросить среднюю школу Франклина К. Лейна. В течение года или двух он подрабатывал помощником грузчика и прессовщиком брюк на швейной фабрике. Его истинным призванием стала работа наемным убийцей в команде Кармине Фатико, которая после убийства Альберта Анастазиа в 1957 году стала частью переименованной семьи Карло Гамбино.
Готти нравилась атмосфера клуба Фатико. Здесь были грубые, остроумные мужчины с готовыми деньгами и большими машинами, которые отдыхали весь день. В отличие от его отца, в округе к ним относились с полным уважением. Для впечатлительного подростка клуб был атрибутом избранного, привилегированного, почитаемого общества, в которое юный Готти хотел попасть.
В разведывательном отчете полицейского управления о банде Фатико 17-летний Готти был отнесен к разряду низкопробных тиро. В течение следующих восьми лет в списке арестов мафиози-новичка значился целый ряд ничем не примечательных преступлений — от уличных драк, опьянения, владения оружием до мелких краж в Нью-Йорке и на Лонг-Айленде. Ни один из арестов не привел к наказанию, превышающему шесть месяцев в окружной тюрьме. В одной из немногих сохранившихся записей, свидетельствующих о ранних выходках Готти, полицейский округа Саффолк Эдвард Халверсон застал его с ломом, врывающимся в таверну в Селдене, Лонг-Айленд, ранним утром 31 марта 1965 года. Когда Готти попытался убежать, Халверсон предупредил: «Не шевелись, иначе я снесу тебе голову». 24-летний будущий дон остановился на месте. «Не беспокойтесь обо мне, — сказал Готти полицейскому. — Беспокойся только об этом пальце».
Несмотря на грязный криминальный послужной список, Готти в конце подросткового возраста завязал важный контакт с мафией, познакомившись с младшим боссом Гамбино, Аниелло Деллакроче. Высокопоставленный мафиози сразу же приглянулся дерзкому молодому Готти, который был достаточно проницателен, чтобы оказывать ему должное почтение при каждой встрече.
Несколько из первых девяти арестов Готти были произведены в компании с Анджело Руджеро, его товарищем по банде и постоянным компаньоном в клубе Фатико. Немного позер, Руджеро побуждал других подражателей ошибочно верить, что он племянник Деллакроче, часто называя его «дядей Нилом». Анджело, известный как «Толстый Энж» за свою тучную фигуру, намекал другим, что его особые отношения с младшим боссом позволили Готти познакомиться с лидером Гамбино номер два. Однако все было наоборот: через Готти Анджело получил возможность познакомиться с Деллакроче.
Бытовая жизнь также приводила Готти в суд. В марте 1962 года он женился на волевом подростке Виктории Ди Джорджио. Ему было двадцать два, ей — девятнадцать. За год до свадьбы у них родилась дочь Анджела. Родители Вики — ее отец был американцем итальянского происхождения, а мать — русского — развелись, и она взяла фамилию отчима после того, как ее мать снова вышла замуж. Из-за арестов Джона, рождения второй дочери и проблем с деньгами первые годы их брака были бурными: несколько раз они расставались, и Вики подала на него в суд за неуплату алиментов.
Новоиспеченный отец уклонялся от решения еще одной проблемы — службы в армии. Он не явился на призыв в армию 22 ноября 1963 года, в день убийства президента Кеннеди, и ФБР настигло его два года спустя. «Готти сообщил, что не осознавал, что просрочил призывную комиссию, так как женат и имеет двоих детей, — говорится в служебной записке ФБР от 7 января 1966 года. — Далее он сообщил, что считает, что из-за этого и того факта, что он ранее был арестован, он не может быть принят в вооруженные силы».
В конце концов, призывные и бытовые проблемы Готти исчезли. Его арест и судимость за кражу машин и ограбление не позволили ему стать солдатом, а размолвка с Вики была облегчена его продвижением по службе в команде Фатико за счет участия в более прибыльных преступлениях: угонах, букмекерстве и ростовщичестве. Отчим Вики, строительный подрядчик, помогал деньгами и ипотекой. Примирившаяся пара и их растущая семья из трех сыновей и двух дочерей стали достаточно благополучными, чтобы переехать из тесной квартиры в собственный комфортабельный дом в Говард-Бич, лиственном районе Квинса, принадлежащем среднему классу.
Говард-Бич находился недалеко от международного аэропорта имени Джона Кеннеди, а также от новой штаб-квартиры команды Фатико. Огорченный наплывом афроамериканцев и латиноамериканцев в Восточный Нью-Йорк, Кармине Фатико, главарь Гамбино, перенес свою штаб-квартиру в витрину магазина в преимущественно белом и итальянском рабочем районе Южный Озон-Парк. Притон был зарегистрирован, как ни странно, в виде некоммерческой ассоциации под названием Bergin Hunt and Fish Club. Название, очевидно, было ностальгическим переиначиванием Берген-стрит в восточной части Нью-Йорка, где располагались корни банды.
Перенос клуба в Южный Озон-парк, расположенный в непосредственной близости от аэропорта Кеннеди, был разумным тактическим решением Фатико. Аэропорт, с его растущим объемом грузовых и пассажирских перевозок, вытеснил бруклинскую набережную как главную цель мафии для грабежей. В 1960-х годах это был крупнейший в мире центр грузовых авиаперевозок, ежегодно переваливавший грузы на сумму более 200 миллионов долларов. Тысячи сотрудников были готовы к эксплуатации в качестве букмекеров и ростовщиков, а также в качестве источника внутренней информации для совершения выгодных преступлений.
Пользуясь богатством аэропорта, Джон Готти, его младший брат Джин и их приятель детства Анджело Руджеро объединились для серии угонов грузовиков. Во время этих угонов Руджеро придумал для Готти личное прозвище «Черный Джон», которое отражало как его грозную личность, так и смуглый цвет лица. Один из мафиози постарше, впечатленный тем, как Готти берет на себя ответственность, дал ему более восхитительное прозвище «Сумасшедший конь», сравнив молодого хулигана с неукротимым индейским воином племени сиу.
Все шло хорошо для трио угонщиков до 1968 года, когда во время операции по пресечению краж в аэропорту агенты ФБР, засевшие в грузовом отсеке, заметили, как братья Готти и Руджеро грузят украденные платья в грузовик U-Haul. Благодаря арестам в аэропорту Кеннеди и с помощью свидетелей, опознавших их по фотороботам, ФБР уличило троицу в трех ограблениях и двух угонах самолетов. Джон Готти, которому на тот момент было двадцать восемь лет, признал себя виновным в своем первом крупном преступлении и был приговорен к трем годам заключения в федеральной тюрьме строгого режима в Льюисбурге, штат Пенсильвания. Его брат Джин и Руджеро получили аналогичные тюремные сроки.
В Льюисбурге Готти столкнулся с Кармином Галанте, зловещей акулой Бонанно, который отбывал наказание за наркотики и фактически был «начальником» мафиозного крыла тюрьмы. Хотя Готти и не был человеком с мировым именем, у него хватило наглости пожаловаться Галанте на то, что тот подкупает охранников, чтобы получить стейки, другие деликатесы и выпивку только для себя и девяти или десяти подручных и подельников Бонанно. Выскочка Готти потребовал, чтобы дон поделился богатством с другими заключенными мафиози. Смелость и самообладание Готти настолько впечатлили Галанте, что он выразил заинтересованность в привлечении его в свою семью. Информаторы сообщили, что Галанте сказал: «Я хотел бы иметь его в своей команде», и был разочарован, услышав, что Джон «принадлежит Нилу», что является отсылкой к Аниелло Деллакроче.
Условно-досрочно освобожденный в 1972 году после трех лет заключения, Готти получил повышение. Капо его команды, Кармине Фатико, был обвинен в ростовщичестве и в ожидании суда должен был держаться подальше от обитателей охотничьего и рыболовного клуба «Бергин», что было условием его освобождения под залог. Когда Готти вернулся домой, Фатико, заручившись поддержкой Деллакроче, назначил его исполняющим обязанности капо, его глазами и ушами, пока не будут решены его юридические проблемы.
