В 1995 году группа побеждает в местном фестивале «Красная РУТА» в Льве.

В 1996 году, группа принимает участие в Таврийских Играх, а также, рядом с другими украинскими группами выступает на одной сцене с Deep Purple во время Осеннего Рока-Марафона в Киеве .

В 1997 году состоялся первый значительный сольный концерт группы в Льве, который собрал 1200 людей.

В 1998 Океан Эльзы начинает работу с продюсером Виталием Климовым (Агентство «Немо») и подписывает контракт с «Новая Рекордс». Группа переезжает в Киев и записывает свой первый альбом «Там, где нас нет». Океан Эльзы начинает концертировать в Москве.

В 1999 году, Океан Эльзы выступили в МСМ Cafe в Париже; выступление транслировалось на телеканале МСМ Іnternatіonal. Группа принимает участие в русском фестивале «Нашествие». На Таврийских Играх, группа получает награду «Открытие Рока».

В 2000, группа выпускает свой второй альбом «Янанебібув». К группе присоединяется Дмитрий Шуров, клавишные. Океан Эльзы принимает участие в фестивале «Максидром» в Москве и выступает в клубе «Асторія» в Лондоне. Во время пребывания группы в Лондоне был снят клип на песню «Тот день». На Таврийских Играх группа получает награду «Лучшая Поп-Группа».

В 2001, группа записывает свой третий альбом, «Модель». Подписывается контракт из Pepsі Cola на общее продвижение альбома и Пепси-Колы; состоялся Всеукраинский концертный тур группы. Журнал NME размещает фото Святослава Вакарчука на обложку своего первого выпуска в России. На Таврийских Играх Океан Эльзы снова получает награду «Лучшая Поп-Группа».

В начале 2002 года, в Барселоне снят клип на песню «Друг». В апреле 2002 года, состоялся концерт группы с Симфоническим Оркестром «Ренесанс» в Дворце «Украина» в Киеве . На Таврийских Играх группа получает награды «Лучшая Рок-Группа», «Лучший Альбом Рока», «Лучшая Песня Рока». Группа продолжает концертировать Россией. В грудные 2002 года выпущен сингл группы, которые состоит из 2 песен. Также в Льве снят клип на песню «Холодно», что вошла в сингл, какой стал девятым клипом группы.