В 1985 году Али отправился в Бейрут, Ливан, вместе с Колбом, Гербертом Мухаммадом и рядом других людей, в том числе с Робертом Сэнси, агентом ЦРУ, которого им представил вице-президент Джордж Буш-старший. Они отправились в столицу Ливана с целью добиться освобождения более сорока заложников, в том числе четырех американцев, удерживаемых мусульманскими экстремистами. Новости того времени посчитали спасательную операцию провалом, но путешествие выдалось более сложным, чем догадывались журналисты. Али и его группа во главе с Сэнси сначала полетели в Лондон, где Али встретился с иранцами, которые, как утверждалось, были близки к верховному лидеру Ирана Рухолле Хомейни – именно его Белый дом считал скрытой рукой, контролирующей захватчиков в Ливане. Колб сказал, что в Лондоне Мухаммед говорил по телефону с Хомейни или с кем-то, кто представился Хомейни. Вскоре после этого один американский заложник был освобожден. Но когда Али сказал репортеру, что его разговор с Хомейни привел к освобождению заложника, миссия застопорилась. Помощники Хомейни сообщили Али, что Иран не имеет никакого отношения к инциденту в Ливане, и предложили Али отправиться в Ливан, если он действительно хотел освободить больше заложников.
В Бейруте американцы посреди ночи были доставлены в конспиративную квартиру «Хезболлы», где произошла встреча с темными фигурами, которые выдвинули условия для освобождения большего количества заложников. Но больше никого не удалось освободить. Каждый день из своего номера в прибрежном отеле «Саммерленд», а также из мечетей и школ, которые он посещал, Али слышал взрывы разрывающихся снарядов и свист пуль. На почтовой бумаге авиакомпании «Мидл Ист Эйрлайнз» он написал письмо своему старому другу Джину Килрою, который из помощника Али превратился в хозяина казино в Лас-Вегасе, обращаясь со своими VIP-клиентами с той же заботой, которую он долгое время уделял Али. Письмо было датировано 20 февраля 1985 года.