1998 року ОЕ розпочав роботу з продюсером Віталієм Клімовим, підписав контракт із «Nova Records» та записав дебютний альбом, який побачив світ у вересні під назвою «Там, де нас нема». Пісні гурту посідали перші місця в чартах, їхня ліричність та незвичайний вокал Святослава Вакарчука здобули шанувальників по всій Україні. У 1999 Океан Ельзи виступив у паризькому МСМ Café (виступ транслював телеканал МСМ International), взяв участь у російському фестивалі «Нашествие». На фестивалі «Таврійські Ігри» музиканти отримали нагороди «Прорив року» та «Найкраща пісня» (за композицію «Там, де нас нема» з однойменного альбому). Саме в цей період майбутній потужній live-звук гурту створив звукорежисер Валерій Папченко. Того ж року відбулося перевидання альбому в Росії. Проте великої популярності «Океан Ельзи» здобув у Росії після виходу фільму Олексія Балабанова «Брат 2» та виходу в ротацію на MTV кліпів «Там, де нас нема» і «Сосни».
На початку 2000-го року гурт завершив роботу над другою платівкою — «Янанебібув», яку випустили одразу на двох звукозаписних студіях — українському Nova Records і російському Real Records. Вже після її випуску (21 лютого) до ОЕ приєднався клавішник Дмитро Шуров (як сесійний учасник) і почалися виступи та репетиції в новому складі. Двічі поспіль (2000 і 2001) на Таврійських Іграх ОЕ був лауреатом у категорії «Найкращий поп-гурт». 2001 року гурт записав найкращий, на думку деяких критиків, альбом української рок-музики — «Модель» (після запису якого Шуров став п'ятим офіційним учасником колективу). Того ж року в рамках співпраці з компанією Пепсі ОЕ гастролював Україною. На Таврійських Іграх-2002 за підсумками 2001 року відразу дві їхні пісні («Друг» і «911») увійшли до списку 10 найпопулярніших хітів України, а «Океан Ельзи» визнали «Найкращим рок-гуртом». «Модель» назвали «Альбомом року». Через рік після виходу платівки «Суперсиметрія» (2003), що вперше в Україні отримала статус двічі платинової, гурт покинули басист Юрій Хусточка і клавішник Дмитро Шуров — обоє взялися за реалізацію проекту «Esthetic Education».

З 2004 року в гурті грають басист Денис Дудко і сербський клавішник Мілош Єліч, який співпрацював із гуртом під час туру «Тихий океан». Перший концерт «Океану Ельзи» в новому складі відбувся в липні в місті Алмати. У квітні 2005-го року гурт покинув гітарист Павло Гудімов, ця подія отримала значний резонанс, оскільки, за словами Гудімова, ініціатором цієї зміни складу був Вакарчук. Але вже через місяць його замінив гітарист Петро Чернявський. 22 вересня 2005 року випущено альбом Gloria, який у перший же день продажу став «платиновим» — за 6 годин було продано 106 000 примірників, а до кінця року вже двісті тисяч.
Вокаліст Святослав Вакарчук як посол доброї волі Програми Розвитку ООН для молоді в Україні взяв участь у багатьох соціальних та культурних проектах. Зокрема, всі кошти, отримані від продажу синґлу «Веселі, брате, часи настали…» було призначено для дитячого будинку в місті Макіївці. 2006 року рок-гурт зіграв безкоштовний концерт для українських миротворців у Косові.
25 квітня 2007 року гурт Океан Ельзи презентував новий альбом «Міра». Новий альбом було присвячено загиблому саундпродюсеру Океан Ельзи Сергію Товстолузькому. Учасники гурту вважають альбом найбільш «роковим» за всю історію команди.
У грудні 2007-го року гурт випустив відео до пісні «Лист до мами», вихід якої був приурочений до Дня Збройних Сил України.
2008 року Святослав Вакарчук презентував джаз-проект «Вночі», випустивши однойменний альбом. Альбом вийшов під ім'ям Святослава Вакарчука як ідейного натхненника, проте над ним працювали всі музиканти О. Е., як і багато запрошених музикантів.
10 березня 2010 року було презентовано сьомий студійний альбом гурту, що отримав назву «Dolce Vita». Альбом містить тринадцять композицій, а також бонусний трек — народну пісню «Ой, чий то кінь стоїть». На підтримку альбому відбувся масштабний (8 місяців) тур «Dolce Vita», що охопив майже 100 міст в Україні, Росії, Білорусі, Європі, Канаді та США. 1 грудня 2010 року було випущено «Dolce Vita (remastered)», зі зміненим звучанням все тих же пісень.

27 лютого 2013 було презентовано відео на перший сингл з нового альбому «Земля», який отримав назву «Обійми́». 11 квітня 2013 року офіційно було оголошено про припинення співпраці між гуртом та гітаристом Петром Чернявським. За офіційним повідомленням, це зумовлено «творчими причинами та прийняте за спільною згодою всіх учасників». У найближчому майбутньому його замінить сербський гітарист Владімір Опсеніца, що брав участь у записі деяких пісень нового альбому.
12 квітня було анонсовано точну дату появи нового альбому та його назву — «Земля». 15 травня 2013 року в мережу інтернет було викладено новий альбом, тоді як компакт-диски в Україні з'являться 20 травня, в інших країнах — 22 травня. 19 травня на підтримку альбому розпочався стадіонний тур. По завершенні української частини туру гурт Океан Ельзи на своєму каналі в YouTube анонсував великий концерт під назвою «Океан Ельзи — 20 років разом!», який відбудеться 21 червня 2014 року у Києві на стадіоні НСК «Олімпійський». Виступи також відбулись на стадіонах Львова, Дніпра, Одеси та Харкова.
14 грудня Океан Ельзи зіграли на підтримку Євромайдану на Майдані Незалежності у своєму «золотому» складі: Вакарчук, Гудімов, Хусточка, Шуров та Глінін.
Заради цього виступу Юрій Хусточка прилетів з Парижа. Свій концерт гурт закінчив зі словами: «Важливі речі об'єднують, пам'ятайте… Дякуємо, все тільки починається!».

В 2014—2015 гурт проводить всеукраїнський тур, приурочений його 20-річчю. 21 червня 2014 в рамках цього туру відбувся концерт у Києві на НСК «Олімпійський». Концерт тривав понад 3 години. Кілька композицій гурт відіграв у старому складі: Святослав Вакарчук, Денис Глінін, Юрій Хусточка, Дмитро Шуров, Павло Гудімов. Єдиним екс-учасником гурту, що не з'явився на сцені, був Петро Чернявський, котрий відіграв у гурті з 2005 до 2013 року. Цей концерт зібрав понад 70 тисяч відвідувачів і став наймасовішим концертом в історії України.
9 червня 2017 року «Океан Ельзи» в рамках свого світового туру «Без меж» виступив з концертом у прифронтовому Лисичанську. Через шалену грозу концерт розпочався замість 20:00 лише о 21:10. Були виконані композиції з останнього альбому «Без меж», а також старі хіти. За інформацією місцевої поліції, на концерті були присутні біля 30 тис. осіб. «Мир прийде тоді, коли кожен з нас як один, як тут — ті, хто стоять на концерті, буде захищати нашу рідну землю, від того, як ми будемо допомагати тим хлопцям, які стоять на передовій, усім, чим можемо», — сказав Святослав Вакарчук.
28.08.2017 фронтмен гурту Святослав Вакарчук на своїй прес-конференції заявив, що група йде у велику творчу паузу довжиною в один рік. «Беремо концертну паузу на рік. Трошки віддихаємось після наших турів, потім подумаємо. Пісень багато нових, зрозуміло, що за певний час новий альбом „Океану Ельзи" планується, в цьому я можу вас запевнити», — сказав він.

29 березня 2018 року група «Океан Ельзи» випустила нову пісню — «Без тебе». — Весна завжди приходить несподівано, — прокоментував Океан Ельзи прем'єру кліпу на офіційній сторінці групи у Facebook. 14 червня відбулася прем'єра другого синглу — «В небо жене». Пісня презентована одночасно в радіо-ефірах країни та онлайн та дебютувала на 1-му місці чарту Google Play. ОЕ повернувся на сцену 24 серпня 2018 року.

21 січня 2019 року в Національній опері України відбувся благодійний концерт «Океану Ельзи» у супроводі оркестру «Віртуози Києва». Майже 4 млн гривень, зібраних з благодійних внесків за квитки на концерт, будуть передані родинам загиблих військових на Сході України через фонд «Народний тил».