Группа «КРУИЗ» сформировалась в 1981 году. В первый состав «КРУИЗА» входили: Валерий Гаина - гитара; Александр Монин - вокал; Сергей Сарычев (в будущем создатель группы «Альфа») - клавишные, вокал; Александр Кирницкий - бас; Всеволод Королюк - ударные; Матвей Аничкин - художественный руководитель.
          В 1981 году группа «КРУИЗ» записала свой первый альбом, получивший название по самой популярной песне из него - «Крутится Волчок». Вскоре были записаны альбомы «Послушай, Человек» и «Красная Книга». Группа утвердилась в выборе стиля — это были миролюбивые песни в хард-роковых и рок-н-ролльных аранжировках с броскими «хитовыми» мелодиями.
          В начале 1983 года группу покинул клавишник Сергей Сарычев, а в «КРУИЗ» влились клавишник Владимир Капустин (экс-«Рок-Сентябрь», Череповец) и гитарист Григорий Безуглый. Таким образом, «КРУИЗ» стал первой в СССР группой с двумя соло-гитаристами в составе. В мае 1983 года с «КРУИЗОМ» расстались Королюк и Кирницкий, а на их место пришли барабанщик Николай Чунусов (экс-«Аракс», «Круг») и басист Олег Кузьмичёв. Этим составом был записан альбом «Путешествие на воздушном шаре» (1983). Однако Валерия Гаину не удовлетворяло звучание и атмосфера внутри коллектива, и он принял решение расстаться с Безуглым. Вместе с Безуглым из «КРУИЗА» ушли также Кузьмичёв, Монин и Чунусов — они покинули группу, чтобы воплотить в жизнь новый проект «ЭВМ».
          Под влиянием веяний времени Валерий Гаина стал экспериментировать в стиле хэви-метал. В начале 1986 года к Валерию Гаине присоединился новый барабанщик Сергей Ефимов, а в декабре 1986 года - новый бас-гитарист Фёдор Васильев (экс-«Черный Кофе»). Музыканты очень хорошо вписались в новый стиль группы «КРУИЗ», который постоянно модернизировался и совершенствовался. С этого момента группа выступала как трио: Валерий Гаина - гитара, вокал; Фёдор Васильев - бас; Сергей Ефимов - ударные.
          Несмотря на столь неожиданные для многих изменения, группа не прекращала давать множество успешных концертов. Теперь уже визитной карточкой «КРУИЗА» стало мастерство каждого из участников группы, артистизм и грандиозное световое и лазерное шоу. В 1986 году был записан первый альбом в новой стилистике. Он получил название по своей заглавной песне - «Рок Навсегда». В 1987 году фирма «Мелодия» выпустила альбом на виниле, исключив из него заглавную песню, и после этого название альбома сменилось на «Круиз-1». Диск пользовался огромным успехом и разошёлся 12-миллионным тиражом, что для 80-х годов было редкостью. Такие песни как «Дальний Свет» и «Пилигрим» стали новой визитной карточкой группы. С этого момента группа считалась лидером стиля хэви-метал в России.
          После было записано еще несколько пластинок и сыграно много концертов, в том числе в странах Европы. Но по ряду причин в конце 1990 года Валерий Гаина принял решение остаться жить и работать в США со своим проектом «GAiNA».
          Прошло много лет, прежде чем Валерий вернулся в Россию. В 2006 году вышел альбом его нового сольного проекта «GAiNA» - «Снова Твой», в 2008 году - альбом «С Кем Ты Играешь и Поешь?!», в конце 2011 года - альбом «Fingertips». В данный момент Валерий Гаина продолжает гастрольную деятельность и приступил к записи четвертого альбома.