Эфрос был прав, утверждая, что в то время «восточный ветер дул в мастерских молодых художников». Павел Кузнецов в поисках ярких впечатлений отправился в заволжские степи, его однокашник по училищу Мартирос Сарьян путешествовал по Ирану и Турции, а саратовский друг Кузьма Петров-Водкин — по Северной Африке.
Восточная тема становится главной в творчестве Кузнецова. «Желая продлить линию Востока, который пришелся мне по нутру, я решил углубиться в Азию: Ташкент, Самарканд, Бухару, — признавался художник. — Два лета подряд я отражал природу и жизнь этого края в своих произведениях. Своеобразный для нас, русских, колорит всего, что там видел, дал новые эмоции и новый подход к живописи».
В путешествиях по Средней Азии Кузнецов открывает иную декоративность. Цветовая гамма его картин уподобляется пестрым восточным коврам: звучные краски и радостный солнечный свет щедро выплескиваются на полотна серии «Горная Бухара». В 1912 году родился цикл «Восточный город», где по тихим узким улочкам плывут луноликие красавицы; в уютных двориках сидят синие павлины; плавятся на солнце бирюзовые мечети; почтенные старики в полосатых халатах ведут неторопливые беседы.
В следующем году художник отправился в Ташкент и древний Самарканд. В жемчужине Великого шелкового пути с изумлением узнал, что самаркандские улицы и площади были выложены камнем за многие столетия до того, как первые мостовые появились в Париже и Лондоне, тогда же в городе Тимура провели первый водопровод. Но самое сильное впечатление на Павла Варфоломеевича произвела «ошеломляюще-гигантская архитектура Тамерлана» — «колоссальные громады» медресе и «монументально вросшие в землю» мечети с устремленными ввысь минаретами. Отныне они часто будут появляться на его рисунках и литографиях.
В 1918-м, на пороге своего сорокалетия, художник Кузнецов по-прежнему был одинок и меньше всего ожидал, что счастливые перемены в его судьбе произойдут именно теперь, когда вокруг царят голод и разруха.