В 1838 г., вскоре после возвращения в Дерпт, В.А. Перовский предложил ему заняться естественно-научным описанием Южного Урала и устройством краеведческого музея, на что Леман с радостью согласился. В марте 1839 г. он покинул Дерпт и отправился на юго-восточную границу России, посетил по дороге Петербург и Казань и прибыл в Оренбург в середине апреля.
В то время А. Леману было 25 лет. Оренбург подарил ему такие яркие впечатления, какие не представлялись начинающему ученому даже в самых смелых мечтах.
В Оренбурге Леман сразу вошел в круг местных краеведов из окружения В.А. Перовского, но особенно близкие отношения связали его с В.И. Далем. Их знакомство началось намного раньше, еще во время учебы Даля в Дерптском университете в 1826-1829 гг.
В письме к сестре от 12 июня 1839 г. Даль пишет: “Прибыл Леман, которого ты, наверное, помнишь по имени по Дерпту, он был в то время маленьким мальчиком, а сейчас он - имеющий мировую славу натуралист, который уже с академиком Бэром побывал на Новой Земле. Приятный, обходительный юноша”[129 ИРЛИ. Письма к сестре П.И. Шлейден.].
О- дружбе Лемана и Даля, их сотрудничестве свидетельствуют, в частности, три неизвестных ранее письма Даля (на немецком языке), обнаруженные в ПФА РАН среди материалов богатого и плохо изученного фонда Лемана[130 ПФА РАН, ф. 6, on. 1, № 5241, л. 452.], много интересных документов, отражающих научную деятельность Лемана, хранится также в ГАОО.
Из документов оренбургского архива мы узнаем о конкретных задачах, которые ставил перед ним В.А. Перовский: “Главною целью занятий Лемана в Оренбургском крае было устройство Оренбургского Музея и составление геогностического описания Южного Урала”. С самого начала Перовский поручил Леману собирать и готовить к экспозиции чучела животных, обитающих в Оренбургском крае, составлять коллекции насекомых и минералов, гербарии и т.д., чем молодой ученый и занялся вскоре после приезда в Оренбург: летом 1839 г. он отправился путешествовать по Южному Уралу и Башкирии для знакомства с природой края. Позднее Перовский уточнил, что от исследователя ожидают не рассказа о путешествии по краю, а научного описания его природы[131 ПФА РАН, ф. 56, on. 1, № 22, л. 2-3.].
В письме к академику Ф.Ф. Брандту от 25 мая В.И. Даль сообщал, что Леман погружен в работу и уже насобирал много прекрасного и интересного. В частности, он нашел, что местный рак относится к виду, еще не описанному, и с его мнением согласен Э.А. Эверсман. Передавая суждения Лемана об ибисе, Даль делает примечание: «Леман протестует против слова “утверждает”, ибо он лишь “предполагает”».
В.А. Перовский возлагал на Лемана большие надежды и в связи с предполагавшейся научной экспедицией к восточным берегам Аральского моря. Однако Леман от этой поездки отказался, но когда в ноябре 1839 г. начался зимний военный поход на Хиву, то Леман стал участником этого похода и впервые получил возможность познакомиться с природой зауральской степи. В труднейших условиях он вел систематические научные наблюдения, о результатах которых сообщал В.И. Даль в письмах к друзьям. К сожалению, дневник, который Леман вел в то время (“Reise nach Chiva”), хранящийся в ПФА РАН, до сих пор не исследован.
Участник Хивинского похода М.И. Иванов вспоминал впоследствии: “Следовавший при отряде естествоиспытатель Леман, человек честный, добросовестный и трудолюбивый, собирал находящиеся в Киргизских степях неизвестные еще тогда и малоизвестные породы животных, растений и минералов [277]. Другой спутник Лемана - молодой офицер Н.П. Иванин рассказал о его работе подробнее: «На обнаженных возвышенностях нам было приказано по пути, для предстоящих зоологических и геологических трудов ученой экспедиции собирать небольшие камни и мышей, на что солдаты наивно смеялись меж собой, говоря: “Чать, не мало и в Питере этой дряни”». Пополнялась и минералогическая коллекция. “По Илеку, Исенбаю и другим речкам, - рассказывает он, - таскали ему плотный кварцевый песчаник, с стекловидным блеском слюду, просто кварц с белыми гальками, серый и желтый полевой шпат, роговую обманку, известняк, асбест, яшму и порфир. У Эмбы окаменелые рыбки нашлись; на стороне Темира я нашел один зуб, да бросил его: он с помощью мороза чуть-чуть не откусил мне пальца. Уральский казак тоже не брал, уверяя, что его потерял киргизский сатана” [278, с. 135].