Связь с «Нацией ислама»

После боя против Листона Клей официально объявил о своём вступлении в «Нацию ислама». Отныне все должны были называть его Кассиус Икс (члены организации отказывались от своей фамилии, потому что считали, что она досталась им от белых рабовладельцев). Малкольм Икс заявил, что Кассиус станет самым важным спортсменом для чернокожих американцев. На встрече в Чикаго Элайджа Мухаммад, который испытывал противоречивые чувства по поводу связей «Нации ислама» с профессиональными спортсменами, радостно встретил молодого чемпиона.

Через две недели после своего вступления Кассиус Икс получил новое имя, Элайджа удостоил чемпиона полного мусульманского имени, которое было зарезервировано для постоянных членов организации. Мухаммад принял спортсмена, назвав его Мохаммедом Али.

Реакция общественности на новость была по большей части негативной. Кассиус-старший заявил, что представители «Нации ислама» «запудрили» его сыну мозги и что он сам будет и дальше с гордостью носить своё имя. Эд Лассман, президент WBA, сказал: «Клей нанёс ущерб боксёрскому миру… и подаёт плохой пример молодёжи». Он попытался лишить Али титула, но это не возымело эффекта, потому что боксёрские комиссии штатов проигнорировали его решение.

Когда Мохаммед посетил один из боксёрских вечеров в Нью-Йорке, Гарри Марксон — президент «Мэдисон-сквер-гарден» — отказался произносить новое имя чемпиона, объявив по громкоговорителю: «В зале присутствует чемпион мира Кассиус Клей». Темнокожие боксёры также отрицательно отнеслись к решению Али. Джо Луис говорил, что он подвёл своих болельщиков, а Флойд Паттерсон написал записку, в которой вызывал чемпиона на бой; как и Луис, Паттерсон считал «Нацию ислама» антиамериканской организацией. Али отреагировал в своей привычной манере, Луиса он назвал «сосунком», а Паттерсону ответил: «Я поиграю с тобой 10 раундов. Ты говорил о моей религии. Я поиграю с тобой. Затем я побью тебя, я обращу тебя».

Перед вторым боем против Сонни Листона, который состоялся в мае 1965 года, Али пришлось сделать трудный выбор. После путешествия Малкольма Икс по Африке и Ближнему Востоку у него изменились взгляды на отношение к белым людям, что привело к нарастающему конфликту с Элайджей Мухаммадом. В итоге Али пришлось выбирать между своими наставниками. Он выбрал Элайджу Мухаммада, открыто поддержав его после второго боя с Листоном.

Разрыв произошёл, когда Али встретился с Малкольмом в аэропорту в Гане. Малкольм поприветствовал, как ему казалось, близкого друга, но Али не подал руки и холодно ответил: «Ты покинул уважаемого Элайджу Мухаммада — это было неправильно». После убийства Малкольма Али говорил: «[Он] был моим другом… До тех пор, пока он оставался членом „Нации ислама“».

Первоначально матч-реванш между Листоном и Али должен был состояться в ноябре 1964 года и пройти в «Бостон-гарден». Но за три дня до проведения поединка у Мохаммеда обострилась кишечная грыжа, и ему пришлось сделать операцию. Бой перенесли на 25 мая 1965 года, но на этот раз вмешалась Массачусетская боксёрская комиссия, которая отказалась санкционировать поединок ввиду возможного влияния на результат преступников. Практически сразу молодой мэр Льюистона, штат Мэн, предложил провести поединок в своём маленьком городке.

В вечер боя небольшая арена не была заполнена до отказа, в зале на 4800 зрителей присутствовало 4200. Ставки букмекеров были 9 к 5 в пользу Листона. Но вопреки их предсказаниям Али нокаутировал противника меньше чем через две минуты после начала боя. Листон рухнул на настил ринга после незаметного удара, в неистовстве Мохаммед отказался идти в нейтральный угол, склонившись над соперником, он закричал: «Вставай и дерись, ты — подонок. Ведь все считают тебя таким плохишом! Да никто не поверит в это!»

Рефери — бывший чемпион мира Джерси Джо Уолкотт — пытался заставить Али отойти в нейтральный угол, вместо этого чемпион танцевал на ринге с поднятыми вверх руками. Затем произошла путаница, Уолкотт наконец добился от Мохаммеда, чтобы он ушёл в нейтральный угол. Всё потраченное на это время судья не открывал счёт. Листон с трудом поднялся, и бой продолжился, но затем Нэт Флейшнер — редактор журнала The Ring — подозвал судью и сообщил ему, что Листон находился на настиле ринга 17 секунд. Уолкотт развёл боксёров по углам, и поединок был официально закончен.

Листон так плохо себя чувствовал, что попросил нюхательной соли, чтобы прийти в себя. Чтобы поддержать Сонни, к нему в раздевалку направился Флойд Паттерсон — человек, дважды побывавший от него в нокауте. Тем временем Али давал интервью на ринге, он сомневался, не упал ли Листон намеренно, но после видеоповтора пришёл к выводу, что это был хороший удар. Позднее Сонни говорил, что удар потряс его, но он не вставал так долго потому, что думал, что Али стал бы добивать его в тот момент, когда он будет подниматься.

После первой защиты титула Мохаммед приобрёл статус звезды мирового бокса, и у него просто не было серьёзных соперников. Никто не хотел третьего боя с Листоном, а два ближайших претендента, Кливленд Уильямс и Эдди Мачен, были недавно биты тем же Сонни. Так как у Али не было реальных соперников, он решил взять отпуск и отправился в мировой тур, в ходе которого он посетил Пуэрто-Рико, Швецию, Лондон и Белиз.

Первой женой Мохаммеда была официантка Сонджи Рой (англ. Sonji Roi), пара поженилась спустя месяц после первой встречи. Наставники Али из «Нации ислама» были озабочены его браком с немусульманской женщиной и в конечном итоге привели его к выбору между религией и женой. 23 июня 1965 года пара подала на развод. Во время своей речи в суде Али особенно подчеркнул нежелание своей жены соблюдать мусульманский дресс-код. Он жаловался, что она оделась слишком откровенно на пресс-конференцию перед вторым боем с Сонни Листоном.

Процесс продолжался до января 1966 года, когда пара официально получила развод