В 1864 году штаб-ротмистр Валиханов участвовал в походе М. Г. Черняева против Кокандского ханства в должности переводчика при главном командовании. Однако туберкулёз прогрессирует и зимой 1865 года он уезжает к родственникам в далекий аул в горах Алтын-Эмеля. Там он женится на Айсары, двоюродной сестре султана Тезека. Семейное счастье было недолгим, болезнь оказалась сильнее. В прощальном письме к отцу Чокан пишет: «Устал, нет никакой силы, весь высох, остались одни кости, скоро не увижу света. Мне больше не суждено повидаться с моими дорогими родными и друзьями, нет для этого никаких средств. Это будет моё последнее письмо. Прощайте, обнимаю». В апреле 1865 года Чокана Валиханова не стало.
«Как блестящий метеор, промелькнул над нивой востоковедения потомок киргизских ханов и в то же время офицер русской армии Чокан Чингисович Валиханов. Русские ориенталисты единогласно признали в лице его феноменальное явление и ожидали от него великих и важных откровений о судьбе тюркских народов, но преждевременная кончина Чокана лишила нас этих надежд. За неполных тридцать лет он сделал то, что другие не смогли сделать за всю свою жизнь». Так писал о Валиханове выдающийся русский востоковед академик Н. И. Веселовский.
В 1867 году, генерал-губернатор недавно образованного Туркестанского генерал-губернаторства Константин Петрович фон Кауфман выделил деньги из казны на строительство мавзолея на могиле Валиханова. Военный губернатор Семиречья Герасим Алексеевич Колпаковский, который был другом Валиханова, заказал в Екатеринбурге плиту и при содействии архитектора Павла Матвеевича Зенкова памятник был сооружён. Кауфман лично контролировал постройку монумента и составил текст надписи на могильной плите. «Здесь покоится прах штабс-ротмистра Чокана Чингисовича Валиханова, скончавшегося в 1865 году. По желанию Туркестанского генерал-губернатора Кауфмана I, во внимание ученых заслуг Валиханова, положен сей памятник генерал-лейтенантом Колпаковским в 1881 году»
С надгробием на могиле связана одна мистическая история. В 1917 году некто захотел сделать из неё жернова для ручной мельницы. Он отбил по периметру большие куски, сбил углы и пытался зубилом и молотком