Обо всем этом Ибн Баттута слышал от заезжих купцов еще в Танжере, а поэтому счел за благо прислушаться к доброму совету и немедленно выступил в путь в надежде догнать посольство на одном из ближайших перегонов.

Из-за болезни Нафарзави посольство задержалось на десять дней в небольшом алжирском городке Мальяна. Старого кадия Ибн Баттута застал в плачевном состоянии. Невыносимый зной, обычный для этих мест в такое время года, усугублял страдания больного, который слабым голосом давал последние наставления своему сыну Абу Тайибу и, судя по всему, готовился предстать перед аллахом. Так оно и случилось, и сразу же после похорон, попрощавшись со своими новыми друзьями, Ибн Баттута двинулся в путь с тунисскими купцами, направлявшимися в Алжир.

Алжир — по-арабски «аль-джазаир» — означает «острова». Так берберский военачальник Бологгин определил несколько мелких островков-скал, торчащих из воды недалеко от порта. Новое название закрепилось за городом, а впоследствии и за всей страной. Это случилось в 935 году, а до этого город назывался Икосиум. В пуническую эпоху здесь, как и в Танжере, находилась процветающая финикийская торговая колония. После падения Карфагена древние римляне превратили город в укрепленную крепость, которая, впрочем, не спасла их от ударов берберов Нумидийского царства. Далее Икосиум пережил события, схожие с теми, что выпали на долю большинства североафриканских городов. Римлян сменили вандалы, вандалов — византийцы, пока наконец в 647 году сюда не пришли арабы.

В Алжире караван пробыл несколько дней. Здесь Ибн Баттуту догнал шейх Зубейди и сын покойного судьи. Посоветовавшись, спутники решили идти до Бужи или Бона вместе с караваном, а там отделиться от него и продолжать путь втроем, так как на дороге из Бона в Тунис, по слухам, в последнее время кочевники совершили несколько особенно дерзких нападений на торговых людей.