Конечно, в этой антипатии ко всему „классическому“ главную роль играли собственные понятия и настроение Верещагина. Но протест против „классицизма“ в художестве был тогда в воздухе — так сильно развилось тогдашнее юношество под влиянием прогрессивных книг и журналов того времени, русских и переводных, под влиянием бесед и прений, происходивших тогда обо всем и повсюду, под влиянием живого обмена мыслей формировавшегося поколения. Не дальше как через несколько месяцев после расправы Верещагина с его „классическим“ картоном, целая толпа молодых людей, которым Академия предложила „классический“ сюжет на 1-ю золотую медаль, отказалась и от сюжета, и от медали, и от возможности ехать на казенный счет за границу; все они вышли из Академии и образовали (1863) художественную „артель“. Современниками Верещагина по Академии были, в это время: во-первых, эти 14 молодых людей, хотя они были все гораздо старше его (Богд. Вениг, Дмитриев-Оренбургский, Литовченко, Песков, Морозов, Корзухин, Крейтан, Шустов, Конст. Маковский, Журавлев, Ник. Петров, Крамской, Лемох, А. Григорьев), а во-вторых, немало выдающихся по даровитости и образованию юных художников, между которыми довольно упомянуть живописца Шварца.
В первую половину 1862 года Верещагин с увлечением слушал лекции Костомарова в Думе и читал почти все, что новая литература давала популярного в науке, чем и пополнил свое корпусное образование.
Однако Верещагин занимался в это время не одним только картоном для Академии. Он работал также и для себя, на свои собственные темы. Так, например, он рисовал дома, пока не наскучило, сцены из русской истории для одного иллюстрированного издания. Брат Александр опять „стоял на натуре“ для сцен: „Тризна на могиле Святослава“ и „Крещение Руси“.
Бросив все это в сторону, Верещагин задумал ехать на Кавказ. Когда он рассказал об этом Львову, тому казалось, что Верещагину еще рано искать самостоятельной работы. „Красок он не знал, — писал мне Ф. Ф. Львов, — он еще недостаточно силен был в работе с натуры, и вообще мне хотелось, чтоб он приобрел более опытности в технике живописи. Но против моего мнения была настойчивая решимость Верещагина: против нее не было достаточно убеждений“. Верещагин оставил Академию и Петербург.
„На Кавказ я приехал, — говорит Верещагин, — летом 1863 года. Чтобы сделать эту поездку, немало времени я питался одним молоком и хлебом и все-таки, приехавши на Кавказ, оказался только с сотнею рублей в кармане. По дороге в Тифлис и в „Белом Ключе“, где жил наместник, великий князь Михаил Николаевич, я, разумеется, много рисовал. Профессор Лагорио, состоявший при великом князе, очень обязательный и добрый человек, рекомендовал меня в семью начальника штаба армии, генерала А. П. Карцева, как учителя рисования“. В этой семье он был принят очень радушно, и с этих пор остался навсегда в самых приятельских отношениях с женою, а потом вдовою этого генерала, Екатериною Николаевною Карцевой. Скоро потом он получил еще уроки: в Межевой школе, в женском училище св. Нины, в военном училище и в одном частном пансионе. Все это вместе давало ему в год около 1500 рублей. Однакоже, как он ни занят был, а все-таки урывался между уроками ходить на „Пески“, рисовать верблюдов, коров, лошадей, баранов и других животных, пригоняемых туда на продажу, рисовать по лавкам, за городом и т. д. „Конечно, только молодость и свобода моя, — говорит Верещагин, — были причиной того, что эта масса уроков не задавила меня. Трудно передать, как я был живуч и как пользовался всяким получасом времени для наполнения моих альбомов. От этого времени, помню, у меня было три толстых книжки совершенно полных рисунками и отчасти акварелями; часто акварелями и карандашом вместе. Все эти альбомы одни потеряны, другие украдены у меня. Я ездил также по Закавказскому краю, рисовал для Общества сельского хозяйства типы животных. Мне дали открытый лист и 400 рублей денег: их, разумеется, нехватило и на прогоны, но зато я много видел и слышал“.
В Тифлисе Верещагин жил в одном доме с профессором Лагорио, с которым познакомился еще у Бейдемана в Петербурге. Днем он был занят уроками и неутомимым своим рисованием с натуры. По вечерам он приходил к Лагорио, читал ему и его жене многие из тех новых иностранных сочинений, которые тогда переводились с такою ревностью и читались нашей молодежью с такой жадностью — она воспитывалась и росла на них. Всего более и чаще читал таким образом Верещагин, в зиму с 1863 на 1864 год, знаменитую книгу Бокля: „История цивилизации в Англии“. Как и все тогдашнее юношество, 20-летний Верещагин был в восторге от этой книги, полной светлых, новых и могучих взглядов на историю и человечество; он с жаром толковал своим собеседникам то, что им было чуждо или непонятно; и особенно много должен был употребить усилий на то, чтобы растолковать им, что такое „индуктивный“ или „дедуктивный метод“, о котором столько говорится у Бокля. Но, кроме симпатичных слушателей и собеседников, Верещагин встречал в этом доме и упорных противников всего нового и свежего. С такими ему приходилось вести ярую войну. Жаркие схватки прогрессиста с консерваторами и ретроградами происходили в эту минуту в Тифлисе точно такие же, какие тогда происходили по всей России, и один из оппонентов Верещагина, редактор одной официальной газеты, клеймил Верещагина модным, тогда еще недавно пущенным в оборот прозвищем „нигилиста“, хотя сам был им отчасти.