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