В Омск, резиденцию Западно-Сибирского губернатора генерала Г. И. Гасфорта, Семенов приехал 1 июня. При встрече с губернатором столичный ученый просил дать ему возможность посетить основанное в 1854 году укрепление Верное (с 1885 года — город Верный, с 1921 года — город Алма-Ата) и изучить Заилийский край, расположенный к югу от реки Или, — геологическое строение, флору и фауну, жизнь населения. Губернатор обещал предписать местным властям, чтобы оказывали содействие исследованиям и предоставляли конвой для поездки в горы. Путешественнику показали карты Семиреченского и Заилийского краев (первый расположен к югу от озера Балхаш до реки Или, а второй — к югу от реки Или до озера Иссык-Куль).

В 1856 году Семенов познакомился с двумя молодыми офицерами: по прибытии в Омск — с Григорием Николаевичем Потаниным, а в конце года в Семипалатинске — с казахом Чоканом Чингисовичем Валихановым. Благодаря знакомству с Семеновым они стали через некоторое время выдающимися путешественниками: Г. Н. Потанин — исследователем Сибири и Центральной Азии, а Ч. Ч. Валиханов — знатоком истории и культуры народов Средней Азии, Казахстана и Западного Китая, в частности казахов и киргизов. Именно Семенов дал совет генералу Г. И. Гасфорту послать поручика Валиханова в экспедицию для изучения ранее абсолютно неизученной области Центральной Азии южнее Тянь-Шаня — Кашгарии.

Из Омска Семенов направился на Алтай. Выехав из Барнаула, он проследовал на юг и вскоре увидел впервые Алтайские горы; осмотрел Колыванское озеро, поразившее его причудливыми формами гранитных скал; в течение месяца посетил ряд заводов и рудников, был в долинах рек Убы и Ульбы; из Риддера (теперь город Лениногорск, в Казахстане) совершил подъем на Ивановский хребет, высочайшие (до 2 275 метров) белки в этом районе (белки — сибирское название горных хребтов, постоянно покрытых снегом, главным образом на Алтае).

Изучив западные окраины Алтая, Семенов взял путь на Семипалатинск, чтобы далее приступить к главному — изучению Тянь-Шаня. В Семипалатинске, в квартире адъютанта губернатора, состоялась неожиданная встреча. Он писал впоследствии: «…Представили одетого в солдатскую шинель дорогого мне петербургского приятеля Федора Михайловича Достоевского, которого я увидел первым из его петербургских знакомых после его выхода из «мертвого дома» — каторжной тюрьмы». А через день Ф. М. Достоевский провожал П. П. Семенова в Семиреченский край.

Из казачьего городка Копал Семенов в сопровождении нескольких казаков совершал восхождение на вершины Джунгарского Алатау (этот хребет, расположенный между озером Алаколь и рекой Или, прежде называли также Семиреченским Алатау); собирал образцы горных пород, коллекцию альпийских растений и насекомых.

В Верном начальник Заилийского края полковник Хоментовский выделил Семенову 10 казаков, двух проводников-киргизов, лошадей и верблюдов, и через два дня он отправился на озеро Иссык-Куль. Возвратившись в Верное и немного отдохнув, Семенов во главе казачьего отряда из 90 всадников начал передвигаться вдоль подножия северной цепи Заилийского Алатау. Такой значительный конвой был необходим из-за возможного нападения враждебных местных племен. Отряд достиг реки Чу и вошел в Буамское ущелье, из которого река вырывается в свою широкую долину.

Семенову удалось разрешить географическую загадку. «Мне хотелось, — писал он, — достигнуть одной из главных целей моего посещения западной оконечности Иссык-Куля. Во время моего пребывания в Берлине (1853 год) географы полагали, что озеро Иссык-Куль имеет сток, но этим стоком одни считали реку Чу, а другие, по распространенным Гумбольдтом сведениям, — речку Кутемалды, которая якобы выходит из озера Иссык-Куль и течет далеко в степь». Проследовав вверх по течению реки Чу, Семенов выяснил: «Главная составная ветвь мощной реки Чу…выходит на Иссык-Кульское плоскогорье, но, не следуя естественному склону к озеру, поворачивает прямо на запад в Буамское ущелье. К востоку от этого поворота я увидел болотистую местность, из которой в Иссык-Куль… текла маленькая речка Кутемалды, имевшая не более шести верст длины… Я доехал до устья речки и, повернув по берегу озера, вернулся в аул Умбет-Алы, вполне убедившись, что озеро Иссык-Куль стока не имеет и что оно в настоящее время не питает реки Чу, и что мощная река эта образуется из двух главных ветвей: Кочкара, берущего начало в вечных снегах Тянь-Шаня, и Кебина, текущего из вечных снегов и из продольной долины Заилийского Алатау».

Перебравшись из Верного в Барнаул, Семенов остался там на зиму и оттуда совершил две поездки: в местность Кату южнее Джунгарского Алатау и на китайскую территорию, в город Кульджа. Цель первой поездки — проверить имевшиеся в китайских источниках упоминания о каких-то вулканических явлениях. Поднявшись в невысокие горы, которые слегка дымились, исследователь нашел месторождения нашатыря и серы. Дымление было связано с горением подземных пластов каменного угля и отношения к вулканическим явлениям не имело. В Кульджу Семенов добрался из Копала через заснеженный перевал Джунгарского Алатау и пробыл в этом городе неделю в качестве гостя российского консула.

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

В то время обстановка в районе Иссык-Куля была тревожной из-за непрекращавшихся стычек между местными казахскими и киргизскими родами. В Верном Семенову был предоставлен конвой из 50 казаков. На этот раз исследователь решил по знакомой уже дороге выйти к восточной оконечности Иссык-Куля, дойти до северного склона снежного хребта, замыкающего бассейн озера с юга, и проникнуть по возможности в его долины и на горные перевалы, соединяющие Илийский и Иссык-Кульский бассейны с китайской провинцией Кашгарией.

29 мая 1857 года отряд Семенова, состоявший из 58 человек и имевший 12 верблюдов и 70 лошадей, двинулся из Верного на юго-восток и пошел через горные перевалы и речные долины Заилийского Алатау. Нужно было проникнуть в глубь Тянь-Шаня по долине реки Заука, впадающей с юга в Иссык-Куль, и через самый доступный из перевалов в этом районе Тянь-Шаня — Заукинский. Удалось благополучно пройти к Заукинскому перевалу, расположенному на высоте более 3 300 метров. Впереди расстилалась равнина с покрытыми снегом вершинами. Между ними лежали озера. Семенов раскрыл еще одну географическую загадку — первым из европейских путешественников добрался до истоков великой среднеазиатской реки.

«Пройдя часа два по этим чудным альпийским лугам, — вспоминал он, — мы взобрались на другой пологий снежный холм, откуда видели еще три озера, из которых речки текли уже на южную сторону перевала, к юго-востоку, и, сливаясь, образовывали более значительную реку, высокая продольная долина которой, направляясь к западу, терялась в туманной дали. Это и была река Нарын, верховье древнего Яксарта, на нижнем течении которого (Сырдарье) Россия уже стояла твердой ногой. Мы проблуждали еще часа два между истоками Нарына, но спуститься вниз по его долине я не решился: лошади наши были измучены и изранены».

В ауле, принадлежавшем одному из киргизских племен, вождь просил Семенова ходатайствовать о принятии его в русское подданство. Путешественник смог нанять 70 свежих лошадей, 10 верблюдов и 6 проводников. Теперь он отправился в северное подгорье Тянь-Шаня, к горной группе Тенгри-Тага.