В этот же период произошла перемена и в его личной жизни: он женился на дочери профессора Армфельдта, Ольге Александровне. Молодая женщина получила естественно-историческое образование, переводила на русский язык работы западных натуралистов, занималась ботаникой. Ольга Александровна дополняла работу мужа, составляя гербарии, ведя экспедиционные дневники и делая зарисовки.
Первая совместная поездка молодых ученых состоялась в 1868 г. Для начала они избрали областью своих исследований Финляндию и Швецию, стремясь собрать в этих странах по возможности многосторонний антропологический материал. Вернувшись в Петербург, Федченко участвовал в I съезде естествоиспытателей, потом побывал с женой в Австрии и Италии.
В 1868 г. московское Общество любителей естествознания решило направить научную экспедицию в долину реки Зеравшана. Алексей Павлович принял предложение возглавить эту экспедицию.
Первая экспедиция в бассейн Зеравшана, в 1869 г., работала в течение 8 месяцев. Федченко собрал огромный гербарий и коллекции насекомых. В следующем году состоялась вторая экспедиция: намечалось закончить исследование Зеравшана и попытаться проникнуть в горные области между Ферганской долиной и Памиром, еще абсолютно никем не исследованные. Зоологическая коллекция исчислялась пятью тысячами экземпляров; гербарии далеко превзошли своими размерами прошлогодние.
Алексей Павлович провел конец лета, осень и зиму в Ташкенте, обрабатывая собранный материал. Часть коллекций следовало выделить для Политехнической выставки в Москве, намеченной на 1872 г. Значительное время Федченко посвятил организации Туркестанского отделения Общества любителей естествознания.
В апреле 1871 г. супруги Федченко предприняли сравнительно небольшую экспедицию – всего только на месяц – в пустыню Кызылкум. Это исследование значительно восполнило пробелы в деле изучения среднеазиатской природы. Но приходилось экономить силы для другого предприятия – самого трудного и самого важного путешествия Федченко, выдвинувшего его в ряды крупнейших исследователей: путешествия в Ферганскую долину и на Алай.
На юге располагалась обширная область, занятая мощной горной системой легендарного Памира. Не только Фергана, но именно эта горная страна особенно привлекала исследователя. Федченко предполагал нанести на карту всю территорию, которую удастся обследовать, изучить орографию страны, ее флору и фауну. Привлекал его также и ряд других проблем: этническая принадлежность, культура и быт среднеазиатских народов интересовали его не меньше, чем строение гор и распространение различных видов насекомых…
В июне 1871 г. экспедиция выступила из Ташкента по Ходжентской дороге. Кое-как добрались до Ходжента, лежащего на левом берегу Сыр-дарьи, за которой возвышаются скалистые утесы Могол-тау. За Ходжентом ландшафт изменился, точно по волшебству. Пашни чередовались с густыми садами, хлопок с пшеницей, селение следовало за селением; оазисы тянулись по правому берегу Сырдарьи сплошной цепью. Прозвище Ферганской долины «Благодатная» казалось вполне оправданным.
В Коканде Федченко получил от хана разрешение продолжать путь по территории Кокандского ханства.
Вскоре ущелье, по которому двигался отряд, замкнулось: его перегораживала серая масса большого ледника. Высота ледяного обрыва равнялась 24 м – шестиэтажному дому. Наутро Федченко решил подняться на ледник втроем со своими русскими спутниками, а Ольга Александровна занялась зарисовкой нижнего конца глетчера.
В честь известного геолога и путешественника, принявшего большое участие в организации экспедиции, открытому леднику – самому значительному из группы глетчеров в истоках реки Исфары – было присвоено имя Щуровского.
Экспедиция двинулась на восток по предгорьям Алайского хребта и вскоре достигла долины Шахимардана. Отсюда должен был начаться самый ответственный этап путешествия – пересечение Алайского хребта.
Селение Шахимардан, в котором остановился Федченко, расположилось у слияния двух горных речек – Аксу и Карасу. На открытой площадке среди садов над маленькой речкой Шахимардан был настоящий рай для натуралиста: такого обилия и разнообразия насекомых Федченко еще не видел нигде. За 6 дней энтомологическая коллекция увеличилась на 1700 экземпляров.
Ольга Александровна помогала Алексею Павловичу в сборе коллекций. Ему удалось поймать новый вид ящерицы, не встречавшейся ранее в Тянь-Шане. Добираться до ящерицы пришлось с риском для жизни по гладкой крутой скале, и Федченко очень гордился приобретением для коллекции единственного экземпляра этого нового вида.
По ущелью, местами имеющему вид гигантского каменного коридора, вверх по течению ревущего горного потока, направлялся путь экспедиции к перевалу Тенгиз-бай в Алайском хребте. Перевал был достигнут через два дня. С его гребня открылась панорама сплошь окутанной белоснежным саваном грандиозной горной цепи, не виденной еще ни одним исследователем. На подступах к этой горной цепи на переднем плане расстилалось степное пространство Алайской долины.