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