Holak dwa lata później wziął ślub, po czym opuścił grupę, a jego zespół przekształcił się w trio. thumb|upright|left|Logo zespołu W marcu 1994 muzycy poznali się z wówczas 19-letnim studentem fizyki teoretycznej Swiatosławem Wakarczukiem, który latem przyszedł na pierwszą próbę, a od jesieni regularnie odbywał próby z zespołem. Nowa grupa, Okean Elzy, została formalnie utworzona 12 października 1994. Zespół grał głównie mieszankę pop i lirycznej muzyki rockowej. Wakarczuk został wokalistą grupy oraz autorem większości tekstów i muzyki zespołu.
W grudniu 1994 zespół nagrał swoje pierwsze cztery demo dla studia „Hałwoks”. Pierwszy poważny występ miał miejsce 12 stycznia 1995 roku przed Lwowską Operą, gdzie zebrało się siedem tysięcy widzów. Tego samego roku, w ramach autorskiego projektu muzycznego „Je” znanego lwowskiego muzyka Ołeha „Johna” Suka zespół nakręcił swój pierwszy nieoficjalny teledysk do piosenki „Long time ago” (reżyserem był Wołodymyr Zajkowski) i wystąpił na festiwalu „Czerwona Ruta” we Lwowie. W 1996 roku grupa wydała maxi-singla „Budynok zi skła”. Począwszy od tego samego 1996 roku, О.Е. zaczął aktywnie koncertować – nie tylko na Ukrainie, ale i w Polsce, Niemczech i Francji, wziął udział w Tawrijskich ihrach (, tł.