В этом была очевидная ирония. То же правительство, которое когда-то преследовало Али за его нежелание участвовать в войне во Вьетнаме, теперь заручилось его помощью, чтобы выдворить Советский Союз из Афганистана. Тем не менее его задача казалась достаточно простой. Должностные лица Государственного департамента проинструктировали Али: все, что от него требовалось, это напомнить африканцам, что Америка – страна свободы, поэтому она не будет молча стоять в стороне и не позволит Советскому Союзу захватить Афганистан. Али стал любимцем Африки задолго до его триумфальной победы над Джорджем Форманом в Заире – он с успехом побывал на континенте еще в 1964 году после победы над Сонни Листоном. Если бы он приехал в Африку и не произнес ни единого слова, а лишь помахал бы толпе и пару раз ударил в воздух, оставив разговоры чиновникам Госдепа, даже так его поездка могла бы обернуться успехом. Но Али был очень впечатлительным, и эта черта характера повредила его дипломатической миссии. Он прибыл на самолете Госдепартамента в Дар-эс-Салам, Танзанию, его первую остановку в туре по пяти странам, и сразу же сел в лужу. Когда танзанийский репортер спросил Али, почему африканцы должны поддержать запрет на московские игры, учитывая, что Москва предоставила помощь ряду освободительных движений в африканских странах, Али с удивлением ответил, что ему не сообщили о поддержке СССР африканских борцов за свободу. «Может быть, меня хотят использовать для чего-то неправильного, – сказал он. – Если я пойму, что ошибся, я отменю поездку и вернусь в Америку». В то же время президент Танзании Джулиус Ньерере отказался встретиться с Али, возмутившись, что президент Картер подослал к нему боксера.

Следующая остановка: Кения, где Али вновь дискредитировал президента Картера, утверждая, что африканские спортсмены должны сами решать, участвовать в московской Олимпиаде или нет. «Я здесь не для того, чтобы навязывать кому-либо свое мнение», – сказал он. Позже Али спросили, почему Соединенные Штаты не поддержали бойкот африканских стран на Олимпийских играх 1976 года в Монреале. Этот протест был связан с тем, что регбийная сборная Новой Зеландии провела матч в ЮАР, которая в тот момент находилась под санкциями Международного Олимпийского комитета. Али сказал, что ничего не знает о бойкоте 1976 года; в противном случае он не предпринял бы свою африканскую кампанию. Журнал «Time» назвал это «самой странной дипломатической миссией в истории США».

Менее чем через месяц после своего возвращения из Африки Али сказал, что хочет снова заняться боксом. Он сказал промоутеру Бобу Аруму, что хочет сразиться с Джоном Тейтом, который держал титул в тяжелом весе Всемирной боксерской ассоциации. Ларри Холмс, бывший спарринг-партнер Али, был чемпионом по мнению Всемирного боксерского совета. У каждой из организации был заведен свой чемпионский титул, поскольку они боролись друг с другом за лидерство.