Четыре друга, Александар Чович (Aleksandar Čović), Борис Милияш (Boris Milijaš), Боян Милияш (Bojan Milijaš) и Горан Лучич (Goran Lučić), в 1989 году решают основать собственную любительскую музыкальную группу. Единственное, чего не хватало группе для начала работы — хороший вокалист. Группа публикует в газетах объявление о прослушивании, но поиски не приносят желаемого результата — отдельные кандидаты даже приходят с чужими записями, выдавая их за свои, чтобы попасть в группу. Участники группы находят Давора Эбнера (Davor Ebner), который в тот момент поет в группе Konvoj («Конвой»). После долгих переговоров, длившихся три месяца, Давор соглашается петь в группе. Чуть позже к группе присоединяется Боян Миличевич (Bojan Miličević).
В 1990 году группа Regina выпускает свой первый одноименный альбом. Александар Чович, автор текстов и музыки, был вдохновлен музыкой ирландской группы U2, что чувствуется в музыкальном стиле группы Regina. На первом альбоме группы хитами становятся песни «Spavaj», «Ne pitaj me» и «Kao nekada ona», для которых снимаются первые видеоклипы. Группу Regina начинают считать новой надеждой музыкальной сцены Югославии.
Вслед за выходом первого альбома группа начинает давать первые концерты. Сначала в Боснии и Герцеговине, затем — на территории всей бывшей Югославии. С самого начала число фанатов группы было столь велико, что вместе с запланированными концертами Regina организовывала дополнительные выступления уже на месте. Слоган, с которым группа представила свой первый альбом, звучал достаточно эксцентрично, чтобы привлечь внимание СМИ: «Мы не Мерлин, мы — Регина» (Dino Merlin — известный на территории Югославии поэт, музыкант и исполнитель). Критики единодушно признали, что Regina стала наследником стиля легендарных групп Indexi и Bijelo dugme. Начинается Reginomanija — так журналисты назвали невероятный интерес со стороны публики к творчеству группы.
В 1991 году выходит новый альбом под названием «Ljubav nije za nas». Хитами становятся песни «Izgledala je malo čudno» (кавер-версия хита популярной югославской группы Bijelo dugme), «Ponekad poželim» и «Ljubav nije za nas». Концертный тур в 1991—1992 годах был самым необычным для любой рок-группы: выступления проходили в городах бывшей Югославии, где уже после 22:00 было запрещено выходить на улицу.
С началом войны в Боснии и Герцеговине группа Regina перестает выступать, кардинально меняется состав: с 1992 по 1999 год Александар Чович и Боян Миличевич продолжают работать уже в Белграде, выпуская альбомы «Oteto od zaborava», «Godine lete», «Ja nisam kao drugi», «Kad zatvorim oci» и «Devedesete». В 2000 году группа распадается.
В 2006 году Александар Чович вместе с Давором Эбнером и Бояном Миличевичем решают снова вернуться на сцену в составе группы Regina. К ним присоединяется Денис Чабрич (Denis Čabrić), который вместе с Давором Эбнером работал над некоторыми менее известными музыкальными проектами. Обновленный состав группы в этом же году представляет новый альбом «Sve mogu ja». Для хитов «Izgledala je malo čudno», «Sama», «Sve mogu ja» и ремикса на песню «Ljubav nije za nas», записанного в дуэте с известной певицей Еленой Ристевски из Македонии, группа снимает высокобюджетные клипы.
В 2007 году группа Regina получает приглашение выступить на одной сцене вместе с легендарными The Rolling Stones на концерте в Будве. Это получасовое выступление становится одним из лучших в карьере группы. С 2007 по 2009 год Regina фактически жила на чемоданах, отыграв больше 200 концертов на территории бывшей Югославии. И снова на их выступлениях нет ни единого свободного места.
12 января 2009 года национальный боснийский телеканал BHT объявляет группу Regina представителем Боснии и Герцеговины на международном музыкальном конкурсе «Eurovision», который в 2009 году проходит в Москве. Официальная песня для конкурса была представлена лишь 1 марта 2009 года. В первом полуфинале группа выступает последней, и благодаря высоким баллам с легкостью попадает в финал. Финальное выступление приносит музыкантам 106 баллов и 9 место. Давор Эбнер по результатам голосования журналистов получает титул «Лучшего певца Евровидения 2009», песня «Bistra voda» становится «Лучшей песней Евровидения 2009», а Александар Чович становится обладателем награды Composer Award Marcel Becanzon как «Лучший композитор Евровидения 2009». В том же году группа Regina выпускает свой 10 студийный альбом «Vrijeme je». На нем, кроме хита «Bistra voda» в трех версиях (оригинальной, английской и русской), еще десять новых песен. Хитами становятся композиции «Bježi dok sam mlad» и «Zvaću te pile moje», для которых группа снимает видеоклипы.
В 2011 году появляется 11 студийный альбом группы «Kad poludimo». Для одноименной песни музыканты снимают видеоклип с участием известной актрисы Нины Янкович (Nina Janković) из Белграда. Позже выходят клипы на песни «Na Balkanu» и «Ptico mala» — дуэт, записанный вместе с певцом легендарной югославской группы «Bijelo Dugme» Младеном Войичичем Тифом (Mladen Vojičić Tifo). В 2014 году группа Regina выпускает сингл «Kalimero», которым заявляет о новом повороте в своей карьере. В 2015 году музыканты отмечают 25-летие на сцене концертом в Сараево. Позже выходит live-альбом с концертной записью и автобиографическая книга Александра Човича, в которой он рассказывает о становлении группы.
В 2016 году группа понесла потерю. 17 августа 2016 года от сердечного приступа в возрасте 49 лет умер Денис Чабрич, бас-гитарист. В 2017 году группа выпустила 12-й по счёту студийный альбом «U Srcu».