В том же 1856 году, по ходатайству Гасфорда, Валиханову был досрочно присвоен чин поручика. К тому времени Чокан был уже действительным членом Русского географического общества, куда был принят по ходатайству виц-президента общества П. П. Семёнова.
Несомненное влияние на Валиханова в то время оказали два человека. Уже упомянутый знаменитый путешественник Пётр Петрович Семёнов (будущий Тян-Шанский), и великий русский писатель Ф. М. Достовский, с которым Чокан познакомился и близко сошёлся в Омске, когда Фёдор Михайлович был освобождён из острога. Позднее они встретились в Семипалатинске, куда Достоевский был сослан рядовым в Седьмой линейный батальон.
В июне 1858 года Чокан Валиханов отправляется с караваном семипалатинского купца Мусабая Тохтубаева в «уйгурские земли». События, подтолкнувшие российское правительство отправить в Кашгар молодого офицера, были следующие. В Западном Китае в 1857 году разразилось восстание мусульманских ходжей против маньчжуров. В результате власть в Кашгаре захватил Валихан-тюря, оказавшийся жестоким тираном. Когда его отряды ворвались в Кашгар, он приказал разграбить лавки, принадлежавшие китайским торговцам, а на берегу реки Кызыл возвел целую пирамиду из отрубленных голов. Жертвой кровавого деспота стал и немецкий путешественник, агент Ост-Индской компании Адольф Шлагинтвейт, которому по приказу Валихана отрубили голову у крепостной стены.
Русское правительство, не имевшее постоянной связи с этим регионом, весьма интересовалось местной обстановкой и поручило Е. П. Ковалевскому подготовить записку со своими соображениями по этому вопросу. В записке, директор Азиатского департамента, отметив важное географическое положение Кашгара, предлагал, под предлогом помощи «законным претендентам» на власть в Западном Китае, вести более активную политику. После обсуждения записки в Министерстве иностранных дел и Военном министерстве было принято решение послать в Кашгар подготовленного офицера для сбора сведений.
После этого Ковалевский пишет письмо генералу Г. Х. Гасфорду, в котором просит помочь найти подходящего человека для отправки в Восточный Туркестан, и вскоре получает ответ: «в выборе чиновника для сего поручения я остановился на состоящем при мне для особых поручений поручике Валиханове. Офицер этот сын достойнейшего киргизского султана Чингиза Валиханова, с очень хорошими дарованиями, и на расторопность его вполне можно положиться. Сверх того, он хорошо ознакомился с историей и нынешним состоянием среднеазиатских владений и, будучи сам мусульманин, скорее русского чиновника может снискать доверие своих единоверцев».
В выборе именно Валиханова, на столь ответственную миссию большую роль сыграл и П. П. Семёнов. В своих мемуарах выдающийся путешественник, впоследствии писал: «Само собой разумеется, что я почёл долгом обратить на этого молодого талантливого человека особое внимание генерала Гасфорта и по возвращении моём в Тянь-Шань подал мысль о командировании Валиханова в киргизской одежде с торговым караваном в Кашгар, что и было впоследствии осуществлено Валихановым с полным успехом».
Все эти события и привели к тому, что июньским утром 1858 года из Семипалатинска в Кашгар отправился торговый караван, в котором находился купец Алимбай Абдиллабаев. Под этим именем скрывался поручик российской армии Чокан Валиханов. Что ждало разведчика «под прикрытием» в далёкой, неизведанной и опасной стране, не знал никто.
Осенью 1858 года, миновав Заукинское ущелье и озеро Иссык Куль, караван с русским разведчиком достиг границ Синьцзяна. Путь был нелёгким. При переходе через заснеженные хребты пала большая часть верблюдов, из сотни голов осталось лишь тридцать шесть. Несколько раз пришлось отбиваться от разбойников, грабивших караваны на торговом пути. Об одном таком нападении можно прочесть в дневнике Валиханова: «Кокандцы напали на караванные стада и отбили 300 баранов. Кашгарцы вступили в драку, вооружившись кольями от своих шатров, и очень скоро обратили в бегство кокандцев».
Не доезжая до Кашгара, дневник, завёрнутый в коленкор и спрятанный в деревянный футляр, пришлось закопать. «Тороплюсь, записывает Валиханов, дневник сейчас зарывается в землю, если бог возвратит нас живыми и здравыми, не испортит сырость, опять покажем белому свету. Поручаю тебя Аллаху, до свиданья».
Не доезжая до Кашгара, дневник, завёрнутый в коленкор и спрятанный в деревянный футляр, пришлось закопать. «Тороплюсь, записывает Валиханов, дневник сейчас зарывается в землю, если бог возвратит нас живыми и здравыми, не испортит сырость, опять покажем белому свету. Поручаю тебя Аллаху, до свиданья».
1 октября караван достиг Кашгара. Чокан, конечно был знаком с книгой Марко Поло «О разнообразии мира» и помнил слова первого европейца, посетившего один из самых знаменитых городов Востока. Восхищённый итальянец писал: «Народ здешний-мусульмане. Городов, городков тут много. Каскар самый большой и самый знатный. Страна тянется на северо-восток и восток, народ тут торговый и ремесленный, прекрасные у них сады, виноградники и славные земли. Хлопку тут родится изрядно. Много купцов идут отсюда торговать по всему свету. Живут тут несториане (одна из ветвей христианства, В.Ф.), у них свои церкви и свой закон. Народ здешний говорит особенным языком. Эта область тянется на пять дней пути».
Несмотря на абсолютную секретность операции, утечка всё же произошла. До Кашгара дошли слухи о приезде переодетого русского офицера и пограничные власти с особым тщанием проверяли все прибывающие караваны. Валиханов, прошёл проверку, и чтобы в дальнейшем не привлекать к себе внимание, вёл себя как настоящий купец: заключал торговые сделки, приобретал товары и даже женился. Речь, конечно, не идёт о выборе спутницы всей жизни. Нет, это был так называемый временный брак весьма распространённое явление на Востоке. Особенно среди купеческого люда, на долгие месяцы отрезанного от дома. Позже Валиханов писал об этом так: «Условие этих браков немногосложно: от мужа требуется одевать и кормить свою жену. В Хотане для того чтобы приобрести жену, нужно сделать расходы на 1 руб. 50 коп. серебром на наши деньги. В Яркенде есть особый базар, где можно встретить женщин, ищущих замужества, и заключить условие; в Аксу и Турфане женитьба стоит дороже. Вследствие этого обычая, хотя представлена женщинам полная свобода выбора и чувств, но по отсутствию образований и понятий о чести проистекает неуважение к брачному союзу, и женщины в Восточном Туркестане не отличаются особенной чистотой нравственности».
Полностью растворившись в купеческой среде, «Алимбай», тем не менее, не забывает о цели своей миссии. «Что касается до моих действий, писал он позднее, то я во время пребывания в Кашгаре старался всеми мерами собрать возможно более точные сведения о крае, особенно о политическом состоянии Малой Бухарии, для чего заводил знакомства с лицами всех наций, сословий и партий, и сведения, полученные от одного, сверял с показаниями другого; сверх того я имел случай приобрести несколько исторических книг, относящихся к периоду владычества ходжей, и пользовался дружбой ученых ахундов Имея постоянные и короткие сношения с кокандцами, я получил много данных о состоянии этого ханства и особенно о последних событиях, имевших последствием падение хана Худояра»
Полгода провёл Валиханов в Кашгарии, находясь в постоянном напряжении, поскольку любой неверный шаг привёл бы к тому, что твоя голова присоединится к пирамиде из других отрубленных голов. И миссию свою русский разведчик выполнил весьма успешно, представив в отчёте ценные военно-политические сведения и массу географического, исторического и этнографического материала. Первый план Кашгара, исполненный по европейскому образцу, был составлен именно Валихановым. Кроме того, он выяснил, что случилось с Адольфом Шлагинтвейном, о чём долгое время в Европе не знали.
Миссия Валиханова явилась первым в России случаем посылки офицера-мусульманина под агентурным прикрытием в политически нестабильный и совершенно неисследованный район Средней Азии. Поездка Адольфа Шлагинтвейна по заданию Ост-Индийской компании и казнённого в Кашгаре в 1857 года и тайная миссия Валиханова в 1858 году знаменовали открытие нового направления англо-русского соперничества в Средней Азии борьбу за доминирование в Восточном Туркестане, борьбу, которая не прекращалась до самых последних дней российской империи.
11 марта 1859 года Валиханов отправляется в обратный путь и через 4 месяца, миновав Верный, прибывает в Семипалатинск. «Судя по отчёту, сделанному Валихановым о Кашгарии, о нём можно судить как о гениальном человеке своего времени», так оценил материалы, представленные разведчиком, директор Азиатского департамента Е. П. Ковалевский. И это отнюдь не преувеличение. По кусочкам, по обрывкам разговоров, по воспоминаниям, по семейным преданиям, русский разведчик нарисовал широчайшую картину жизни Кашгара. При том, что, собирая и сопоставляя клочки сведений, он не везде и не всегда мог вести подробные записи. Огромную часть материалов он хранил в памяти.