Aleksandar Čović, Goran Lučić, and the Milijaš brothers began a garage band. After searching, they found Davor Ebner, who became their lead singer. Bojan Milićević joined the group in 1990 (before the release of the first album). Once the band was created, it was successful all over Yugoslavia with the slogan "MI NISMO MERLIN, MI SMO REGINA" ("We aren't Merlin, we're Regina").
When the Yugoslav wars began in Bosnia and Herzegovina, Serb members of the band fled to Belgrade, where Regina continued until 2000, when Čović started his solo career. In 2006, the band reunited with the original members and appeared at a Serbian radio festival organized by Radio S. In 2007 they were an opening act at Rolling Stones concert at Jaz beach, Budva, Montenegro.
In 2009 they represented Bosnia and Herzegovina in the Eurovision Song Contest 2009 with their song "Bistra Voda".