За следующие пять лет он успел влюбиться в Северную столицу. И все же самой большой любовью оставался Крым. Командированный в Феодосию, через год он отправил в Академию пять картин и просьбу не отзывать его в столицу на зимние месяцы, а позволить участвовать в военных операциях начальника Черноморской прибрежной линии генерала Николая Раевского. Сыну героя 1812 года было доверено окончательное замирение Кавказа. Гайвазовский ходил на пароходе «Колхида» вместе с Раевским, потом перешел к капитану Павлу Нахимову на линейный корабль «Силистрия». Он совершил три десанта на черкесский берег: с пистолетом и рисовальными принадлежностями наперевес участвовал в мелких стычках по усмирению горцев.
Когда летом 1840 года Иван вернулся в Петербург, две его лучшие картины «Десант Н.Н. Раевского в Субаши» и «Вид Севастопольского рейда с военными судами» удостоились чести быть представленными императору Николаю I. Но Гайвазовский вновь засобирался в дорогу — на этот раз наконец в Европу.
Первым пунктом путешествия стала Венеция. Много лет назад именно туда знакомый купец увез учиться старшего брата Ивана. За годы разлуки жизнерадостный Гарик превратился в бесстрастного монаха — архимандрита Гавриила, насельника армянского монастыря Cвятого Лазаря. Братья проговорили весь день. На ночь Ивана разместили в келье, где когда-то лорд Байрон изучал старинные рукописи и работал над армяно-английским словарем. Гайвазовский объездил всю страну, работая со страстью одержимого и прерываясь только на сон. Готовые картины отсылал в Петербург, но некоторые демонстрировал и в Италии. Три работы, выставленные в римской галерее, принесли ему настоящую славу. Одну из них, «Хаос. Сотворение мира», со светящимся силуэтом Бога-творца над морскими волнами приобрел папа римский Григорий XVI для галереи Ватикана. После этого художника стали называть первым европейским маринистом. В кафе, где Иван обедал, потянулись зеваки: всем хотелось посмотреть на знаменитость. Сотрапезники Гайвазовского писатель Николай Гоголь и художник Александр Иванов никого не интересовали.