Встретившись с Александром Егоровичем Бейдеманом, Василий услышал от бывшего наставника, что генерал Константин Петрович Кауфман, только что назначенный командующим войсками Туркестанского военного округа и генерал-губернатором Туркестана, подыскивает художника, который смог бы отправиться вместе с ним в Среднюю Азию. Воодушевленный перспективой увидеть новый, загадочный край, Верещагин через петербургских друзей добился встречи с Кауфманом и показал ему свои рисунки. Энергичный молодой художник произвел на Кауфмана благоприятное впечатление. 22 августа 1867 года состоялось официальное назначение прапорщика Верещагина на службу при генерал-губернаторе Туркестана. Вспоминая то время, художник писал, что Кауфман обещал ему частые поездки по краю. С целью сохранить относительно независимое положение Василий выговорил у генерал-губернатора разрешение не носить форму и добился от него обещания не давать ему очередные чины. Фактически он отправлялся в путь на правах прикомандированного к высокому начальству вольного художника, призванного запечатлеть пейзажи, постройки, одежду и, самое главное, людей, населявших присоединяемые к России территории. Подобным же образом мореплаватели прежних времен, отправляясь открывать новые земли и знакомиться с проживавшими на них племенами, брали на свои корабли живописцев, чтобы по окончании путешествий предоставить наглядный отчет обо всем, что было ими увидено и открыто в дальних странствиях. Но у Верещагина помимо интереса к изображению мирной жизни «туземцев» был иной мощный стимул для поездки в Азию. «…Хотел узнать, — писал он, — что такое истинная война, о которой много читал и слышал и близ которой был на Кавказе» [56].
Завершив длительную Кавказскую войну, Россия получила возможность резко усилить свою активность на другом направлении, которое считала чрезвычайно важным, — в Средней Азии. Крестьянская реформа дала толчок развитию промышленности и торговли. Империя нуждалась и в новых рынках сбыта, и в источниках сырья, и в людских ресурсах для освоения присоединяемых территорий. Обширные среднеазиатские регионы могли дать и то, и другое, и третье — если, конечно, поторопиться, не позволив чересчур активной в этом регионе Англии опередить себя. А англичанам мало было Индии. Они ведут войны уже и в Иране, и в Афганистане. Если промедлить, британские подданные вскоре окажутся у российских границ. Русское правительство медлить не стало, и в июле 1865 года войска генерала Н. Г. Черняева вошли в Ташкент. Год спустя этот город стал центром Туркестанской области в составе Оренбургского генерал-губернаторства. А в июле 1867 года было принято решение образовать новое генерал-губернаторство — Туркестанское — с двумя областями: Сырдарьинской и Семиреченской. Генерал-адъютант Кауфман был назначен руководителем нового территориального образования России лично Александром II. При этом учитывался его достойный послужной список: более чем десятилетнее участие в Кавказской войне (где он проявил и способности военачальника, и личную храбрость) и его административный дар (Кауфман послужил виленским, ковенским, гродненским генерал-губернатором). Сочетание административных талантов с качествами опытного военачальника в данном случае было как нельзя кстати, тем более что на новом посту К. П. Кауфман получил полномочия для расширения и укрепления новых границ Российской империи.
«От Оренбурга до Ташкента» — так озаглавил Верещагин свои путевые очерки, которые он опубликовал сначала в ряде петербургских газет, а затем, в полном виде и со своими рисунками, — в журнале «Всемирный путешественник». Выехав из Петербурга в конце августа 1867 года, он на шестой день, в сентябре, прибыл в Оренбург. Художник прожил там несколько дней и, двинувшись далее, на юго-восток, 19 ноября достиг Ташкента — столицы нового генерал-губернаторства.
Занимаясь по пути привычным для себя делом и одновременно выполняя поручение Кауфмана, он заполнял альбомы многочисленными рисунками. Подписи под ними указывают или национальность человека, или географию места. Так появились рисунки «Голова казаха в войлочной шляпе», «Узбек в чалме», «Богатый казах в тюбетейке», «Старая крепость по дороге из Чимкента в Ташкент», «Постоялый двор близ Ташкента», «Мечеть в городе Туркестане», «Казахские кибитки»…