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

Несколько из первых девяти арестов Готти были произведены в компании с Анджело Руджеро, его товарищем по банде и постоянным компаньоном в клубе Фатико. Немного позер, Руджеро побуждал других подражателей ошибочно верить, что он племянник Деллакроче, часто называя его «дядей Нилом». Анджело, известный как «Толстый Энж» за свою тучную фигуру, намекал другим, что его особые отношения с младшим боссом позволили Готти познакомиться с лидером Гамбино номер два. Однако все было наоборот: через Готти Анджело получил возможность познакомиться с Деллакроче.

Бытовая жизнь также приводила Готти в суд. В марте 1962 года он женился на волевом подростке Виктории Ди Джорджио. Ему было двадцать два, ей — девятнадцать. За год до свадьбы у них родилась дочь Анджела. Родители Вики — ее отец был американцем итальянского происхождения, а мать — русского — развелись, и она взяла фамилию отчима после того, как ее мать снова вышла замуж. Из-за арестов Джона, рождения второй дочери и проблем с деньгами первые годы их брака были бурными: несколько раз они расставались, и Вики подала на него в суд за неуплату алиментов.

Новоиспеченный отец уклонялся от решения еще одной проблемы — службы в армии. Он не явился на призыв в армию 22 ноября 1963 года, в день убийства президента Кеннеди, и ФБР настигло его два года спустя. «Готти сообщил, что не осознавал, что просрочил призывную комиссию, так как женат и имеет двоих детей, — говорится в служебной записке ФБР от 7 января 1966 года. — Далее он сообщил, что считает, что из-за этого и того факта, что он ранее был арестован, он не может быть принят в вооруженные силы».

В конце концов, призывные и бытовые проблемы Готти исчезли. Его арест и судимость за кражу машин и ограбление не позволили ему стать солдатом, а размолвка с Вики была облегчена его продвижением по службе в команде Фатико за счет участия в более прибыльных преступлениях: угонах, букмекерстве и ростовщичестве. Отчим Вики, строительный подрядчик, помогал деньгами и ипотекой. Примирившаяся пара и их растущая семья из трех сыновей и двух дочерей стали достаточно благополучными, чтобы переехать из тесной квартиры в собственный комфортабельный дом в Говард-Бич, лиственном районе Квинса, принадлежащем среднему классу.

Говард-Бич находился недалеко от международного аэропорта имени Джона Кеннеди, а также от новой штаб-квартиры команды Фатико. Огорченный наплывом афроамериканцев и латиноамериканцев в Восточный Нью-Йорк, Кармине Фатико, главарь Гамбино, перенес свою штаб-квартиру в витрину магазина в преимущественно белом и итальянском рабочем районе Южный Озон-Парк. Притон был зарегистрирован, как ни странно, в виде некоммерческой ассоциации под названием Bergin Hunt and Fish Club. Название, очевидно, было ностальгическим переиначиванием Берген-стрит в восточной части Нью-Йорка, где располагались корни банды.

Перенос клуба в Южный Озон-парк, расположенный в непосредственной близости от аэропорта Кеннеди, был разумным тактическим решением Фатико. Аэропорт, с его растущим объемом грузовых и пассажирских перевозок, вытеснил бруклинскую набережную как главную цель мафии для грабежей. В 1960-х годах это был крупнейший в мире центр грузовых авиаперевозок, ежегодно переваливавший грузы на сумму более 200 миллионов долларов. Тысячи сотрудников были готовы к эксплуатации в качестве букмекеров и ростовщиков, а также в качестве источника внутренней информации для совершения выгодных преступлений.

Пользуясь богатством аэропорта, Джон Готти, его младший брат Джин и их приятель детства Анджело Руджеро объединились для серии угонов грузовиков. Во время этих угонов Руджеро придумал для Готти личное прозвище «Черный Джон», которое отражало как его грозную личность, так и смуглый цвет лица. Один из мафиози постарше, впечатленный тем, как Готти берет на себя ответственность, дал ему более восхитительное прозвище «Сумасшедший конь», сравнив молодого хулигана с неукротимым индейским воином племени сиу.

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