Потанин активно сотрудничает с иркутской газетой «Сибирь», публикуя свои материалы без подписи или под псевдонимом «Авесов»: «Крымские письма сибиряка», «Роман и рассказ в Сибири», «Из путевых заметок сибиряка» и др.

Семенов предлагает Потанину возглавить научную экспедицию в северо-западную Монголию, в горы Монгольского Алтая. Большую часть средств выделило ИРГО, в размере 3000 рублей, дополнительно – министерство финансов на изучение монгольского товарного рынка спроса-предложения. В министерстве иностранных дел Потанин получает разрешение на самостоятельные экспедиции за границу в качестве руководителя.

Потанины на период подготовки экспедиции переехали в Омск, откуда традиционно начинались экспедиции в Монголию, на Памир и Тянь-Шань. Потанин оставляет запись в дневнике: «Мне всегда Омск казался, а теперь ещё больше кажется, похожим на старую шинель Акакия Акакиевича».

20 июля 1876 года отряд вышел из города Зайсан (Ныне административный центр Зайсанского района Восточно-Казахстанской области, Казахстан) у подножия Алтайских гор. Шли на восток долиной реки Черный Иртыш.

Досаждали мириады комаров, шум в воздухе стоял, как от кипящего самовара, такой образ родился у Александры Викторовны. В день проезжали до тридцати верст.

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

Александра Викторовна отвечала за хозяйственную и бытовую часть экспедиции, она была и казначеем экспедиции, и поваром, и снабженцем. Она также стирала (мыла) белье свое и мужа, и готовила на весь отряд, включая погонщиков или носильщиков.

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

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

По впечатлениям Потанин запишет в дневнике: «Я здесь наткнулся на странные факты, которые меня на первых порах удивляли. Мне кажется, что здесь живут свежо остатки древности, предшествующей самой ранней цивилизации. Может быть, я ошибаюсь, но мне представляется, что здешние легенды н верования древнее семитических и, зародившись здесь, перешли вместе с переселением семитов на Запад. Предание о Адаме и Еве находит здесь свое начало в местном языке, на языке кокчулутунов или урянхайцев. Отец называется «адам», мать – «емь»… Да, эта местность, где мы живем, настоящая родина человека. Здесь возник первый культ… Реки здешние представлялись первым людям материнскими лонами, отцов они видели в горных вершинах. Рай Адама и Евы, я теперь уверен, находился в верховьях Иртыша, на берегах которого я родился… Самое название реки Эбин не напоминает ли Эдем?…»

С середины октября 1876 года и по март 1877 года экспедиция зимовала в Кобдо, собирая материалы о русско-монгольской торговле и жизни русских и китайцев в Монголии. Старейший монгольский город, основан в 1685 году, исторически был торговой столицей последнего независимого государства кочевников Джунгарского (Ойратского) ханства, и одним из центров Шелкового пути в Центральной Азии. Расположен на реке Кобдо-Гол (ныне река Ховд, одна из главных рек Монголии). Несколько веков джунгары наводили ужас на жителей Центральной и Средней Азии беспощадной жестокостью во время стремительных и яростных нападений.

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