Родители Верещагина были очень недовольны его выходом в отставку. Когда только что пошла речь об этом, мать, Анна Николаевна, страстно любившая своего Васю, но не воображавшая, что сын ее — великий талант, прямо говорила, что считает это сущим сумасшествием. Отец менее перечил, но помогать деньгами отказался, чтобы не потакать отставке. Они оба говорили ему: „Подумай, Вася, хорошенько; ведь рисование не даст тебе хлеба и не введет в гостиные“. Но он не слушался никаких уговариваний и твердо стоял на своем. В своем затруднительном положении он пошел сперва к известному железнодорожному деятелю Колиньону, просить занятий по чертежной и рисовальной части, а затем к своему покровителю Львову, рассказал дело и просил совета. Этот, хотя и убежденный в таланте Верещагина, тоже сначала отговаривал его бросать морскую службу и променивать верное на неверное. Но потом, видя непреклонную решимость юного художника, сказал ему: „Уладим дело, дадим вам пенсию; приходите, как выйдете из корпуса“.
„Новеньким, чистеньким гардемарином, с аксельбантом и треугольной шляпой, явился я к нему весной 1860 года, — рассказывает Верещагин. — Львов (ставший с 1859 года конференц-секретарем Академии художеств) представил меня вице-президенту князю Гагарину и объявил, что я буду получать от Академии по 200 рублей в год в продолжение двух лет. Теперь, когда я пишу вам это, у меня слезы на глазах. Спасибо Львову, спасибо до конца моей жизни!“
После выпуска из корпуса Верещагин тотчас же вышел в отставку. Осенью того же 1860 года он поступил в Академию художеств в число учеников профессора Маркова. Кроме того, Львов просил адъюнкт-профессора Бейдемана им заняться. „Бейдеман, тогда еще свежий, — рассказывает Верещагин, — был мне очень полезен. Он первый рядом наглядных примеров поколебал мою веру в необходимость „штриха“, чистоты и опрятности рисунка. Я стал рисовать грязнее и стал получать более далекие нумера; однако за последние два рисунка в гипсовых фигурах опять имел нумер 1, первым же перешел и в натуральный класс“ (за рисунок торса Геркулеса).
„Со времени знакомства с Бейдеманом, — продолжает он, — я очень много рисовал на улице и прямо с натуры, а еще более на память, все виденное и замеченное. Как было тут не опошлеть в моих глазах псевдоклассицизму?..“
Бейдеман незадолго перед тем, только в июле 1860 года, воротился из большого заграничного путешествия по Германии, Италии и Франции, где он пробыл целых три года. Его рассказы о новом французском искусстве и художниках сильно подействовали на Верещагина. „В 1861 году я сколотил гроши, — рассказывает он; — дядя Алексей Васильевич Верещагин (очень богатый человек, отставной лейб-гусар и большой кутила) прислал 100 рублей да отец дал столько же, и я через Штеттин и Берлин поехал в Париж, откуда, за болезнью, пробрался до Пиринеев (Eaux-Bonnes). Думаю, что виденное за границей было мне полезно“.
Весной 1861 года Верещагину надо уже было перейти в Академии из 1-го отделения во 2-е; но так как он, по случаю своего заграничного путешествия, не явился на экзамен по некоторым предметам и потому не имел среднего балла, то совет Академии определил: допустить его до экзаменов осенью того же года.
Воротясь через несколько месяцев в Петербург, Верещагин сделал последнюю попытку в классическом роде: он принялся за большую композицию на медаль. Эта медаль подорвала недоверие к его силам даже у матери и она благословила его на дальнейшие занятия. Заданный сюжет был: „Избиение женихов Пенелопы возвратившимся Улиссом“. За эскиз Академия дала ему 2-ю серебрянную медаль, после третного экзамена в декабре 1862 года. Потом Верещагин вздумал трактовать тот же сюжет в огромных размерах, в виде картона в 5 аршин ширины, писанного сепией. Исполнялся он по-всегдашнему, в особом помещении, отведенном в Академии. Моделями служили Верещагину, кроме академических натурщиков, его братья Александр и Михаил; первый стоял „на натуре“ для всех главных фигур: Улисса, Телемака и Антиноя, которого Улисс пронизывает стрелой в ту минуту, когда тот собирается пить чашу с вином. Вся композиция была подражание Флаксману. За эту работу совет Академии после третного экзамена, в мае 1862 года, объявил Верещагину „похвалу“. Но он сам был недоволен картоном. Он разрезал его на куски и бросил в печку, а когда товарищи и Бейдеман удивлялись, зачем он это сделал, — „бумага-то ведь не виновата“, то он отвечал: „А это для того, чтоб уже наверное не возвращаться к этой чепухе!..“