В 1856 году Семенов познакомился с двумя молодыми офицерами: по прибытии в Омск — с Григорием Николаевичем Потаниным, а в конце года в Семипалатинске — с казахом Чоканом Чингисовичем Валихановым. Благодаря знакомству с Семеновым они стали через некоторое время выдающимися путешественниками: Г. Н. Потанин — исследователем Сибири и Центральной Азии, а Ч. Ч. Валиханов — знатоком истории и культуры народов Средней Азии, Казахстана и Западного Китая, в частности казахов и киргизов. Именно Семенов дал совет генералу Г. И. Гасфорту послать поручика Валиханова в экспедицию для изучения ранее абсолютно неизученной области Центральной Азии южнее Тянь-Шаня — Кашгарии.
Из Омска Семенов направился на Алтай. Выехав из Барнаула, он проследовал на юг и вскоре увидел впервые Алтайские горы; осмотрел Колыванское озеро, поразившее его причудливыми формами гранитных скал; в течение месяца посетил ряд заводов и рудников, был в долинах рек Убы и Ульбы; из Риддера (теперь город Лениногорск, в Казахстане) совершил подъем на Ивановский хребет, высочайшие (до 2 275 метров) белки в этом районе (белки — сибирское название горных хребтов, постоянно покрытых снегом, главным образом на Алтае).
Изучив западные окраины Алтая, Семенов взял путь на Семипалатинск, чтобы далее приступить к главному — изучению Тянь-Шаня. В Семипалатинске, в квартире адъютанта губернатора, состоялась неожиданная встреча. Он писал впоследствии: «…Представили одетого в солдатскую шинель дорогого мне петербургского приятеля Федора Михайловича Достоевского, которого я увидел первым из его петербургских знакомых после его выхода из «мертвого дома» — каторжной тюрьмы». А через день Ф. М. Достоевский провожал П. П. Семенова в Семиреченский край.
Из казачьего городка Копал Семенов в сопровождении нескольких казаков совершал восхождение на вершины Джунгарского Алатау (этот хребет, расположенный между озером Алаколь и рекой Или, прежде называли также Семиреченским Алатау); собирал образцы горных пород, коллекцию альпийских растений и насекомых.
В Верном начальник Заилийского края полковник Хоментовский выделил Семенову 10 казаков, двух проводников-киргизов, лошадей и верблюдов, и через два дня он отправился на озеро Иссык-Куль. Возвратившись в Верное и немного отдохнув, Семенов во главе казачьего отряда из 90 всадников начал передвигаться вдоль подножия северной цепи Заилийского Алатау. Такой значительный конвой был необходим из-за возможного нападения враждебных местных племен. Отряд достиг реки Чу и вошел в Буамское ущелье, из которого река вырывается в свою широкую долину.
Семенову удалось разрешить географическую загадку. «Мне хотелось, — писал он, — достигнуть одной из главных целей моего посещения западной оконечности Иссык-Куля. Во время моего пребывания в Берлине (1853 год) географы полагали, что озеро Иссык-Куль имеет сток, но этим стоком одни считали реку Чу, а другие, по распространенным Гумбольдтом сведениям, — речку Кутемалды, которая якобы выходит из озера Иссык-Куль и течет далеко в степь». Проследовав вверх по течению реки Чу, Семенов выяснил: «Главная составная ветвь мощной реки Чу…выходит на Иссык-Кульское плоскогорье, но, не следуя естественному склону к озеру, поворачивает прямо на запад в Буамское ущелье. К востоку от этого поворота я увидел болотистую местность, из которой в Иссык-Куль… текла маленькая речка Кутемалды, имевшая не более шести верст длины… Я доехал до устья речки и, повернув по берегу озера, вернулся в аул Умбет-Алы, вполне убедившись, что озеро Иссык-Куль стока не имеет и что оно в настоящее время не питает реки Чу, и что мощная река эта образуется из двух главных ветвей: Кочкара, берущего начало в вечных снегах Тянь-Шаня, и Кебина, текущего из вечных снегов и из продольной долины Заилийского Алатау».
Перебравшись из Верного в Барнаул, Семенов остался там на зиму и оттуда совершил две поездки: в местность Кату южнее Джунгарского Алатау и на китайскую территорию, в город Кульджа. Цель первой поездки — проверить имевшиеся в китайских источниках упоминания о каких-то вулканических явлениях. Поднявшись в невысокие горы, которые слегка дымились, исследователь нашел месторождения нашатыря и серы. Дымление было связано с горением подземных пластов каменного угля и отношения к вулканическим явлениям не имело. В Кульджу Семенов добрался из Копала через заснеженный перевал Джунгарского Алатау и пробыл в этом городе неделю в качестве гостя российского консула.
В 1857 году П. П. Семенов отправился из Барнаула в Заилийский край в сопровождении художника П. М. Кошарова. Путешественники добрались до ущелья, через которое пробивается река Или, и, найдя на высоком утесе огромные знаки тибетской надписи, зарисовали их.