Наконец, подготовка была закончена, и Алексей из Парижа отправился в Марсель, где его ожидал пароход, отплывающий к североафриканскому берегу.

Наконец, 44-часовое плавание осталось позади и перед русским офицером открылся во всей красе город Алжир. «Скоро можно было распознать, – пишет Куропаткин, – две резко одна от другой отличающиеся части его: европейскую и туземную. Первая занимает ближайшую к морю часть города, вторая амфитеатром идёт в гору и венчается старой турецкой крепостцою (Касба). Роскошные пятиэтажные дома набережной, станция железной дороги, ряды вагонов, масса французских и иностранных судов в порту, оживлённая выгрузка и нагрузка товаров, всё это сразу давало понять, что Европа с её лихорадочной деятельностью, уже прочно оселась в этом уголке Африки».

Не откладывая дел в долгий ящик, Алексей отправился представляться французским властям. Генерал-губернатор Шанзи отсутствовал и русского офицера принял, временно исполняющий его обязанности начальник дивизии. Принял, надо сказать, весьма радушно. Подробно расспросив о цели приезда, он обещал полное содействие, прося только заблаговременно уведомить о маршруте следования. Затем был вызван адъютант, в чине капитана, которому было поручено познакомить русского гостя с офицерским обществом Алжира, а также сопровождать того при осмотре военных заведений. Завершил аудиенцию французский генерал следующими словами: «Уже одного того, что вы носите русский мундир, совершенно для нас достаточно, чтобы оказать вам возможно широкое гостеприимство».

Почти два месяца пробыл Куропаткин в столице французского Алжира. За это время он перезнакомился со всеми офицерами местного гарнизона, посетил расположение различных частей и родов войск, с интересом наблюдал за погрузкой на суда трёх батальонов пехоты, свободно получая все интересующие его сведения. Как он записал позже: «Вообще, я считаю своим долгом упомянуть, что, благодаря моему русскому мундиру, не только власти военные, но и гражданские встречали меня весьма радушно, и предупредительно сообщали все сведения, которые были мне необходимы».

В ноябре 1874 года Алексей отправился в город Тлемсен, расположенный на северо-западе страны. Там располагался полк африканских егерей и пехотный батальон. И здесь русский гость был принят со всем радушием и без всяких препон получил всю необходимую информацию. Затем был город Лагуат, на самой границе с пустыней Сахарой, где Куропаткин осмотрел два форта и пообщался с гарнизоном. Знакомый не понаслышке с песками Туркестана, он живо интересуется формированием максимально приспособленного к условиям пустыни верблюжьего обоза, вместо используемого в туркестанских войсках конного. И эта информация была учтена в следующих походах русской армии в Средней Азии. Кроме чисто военных вопросов, русского офицера интересуют быт и обычаи местного населения, климат, растительность, животный мир. Всё это позже будет отражено в первом научном труде Алексея Николаевича, написанного по результатам поездки – «Алжирия».

В январе 1875 года Куропаткин возвращается в столицу Алжира и приступает к обработке собранного материала. Вскоре, ему удаётся поучаствовать в походе французских войск под командованием генерала Лавердо. Похода мирного. Целью экспедиции в Большую Сахару явилось исследование территории площадью 75 тысяч квадратных километров. Русский офицер не получил никаких привилегий. Он, имея пятилетний опыт Туркестанских походов, мужественно переносил все тяготы: песчаные бури, долгие утомительные переходы, суровый быт лагерной жизни, неся службу наравне с французскими военнослужащими. К концу похода французы считали его своим, чему способствовало коммуникабельность, тактичность Алексея, а также блестящее владение им французского языка.