The group's core consisted of singer and guitarist Milan Mladenović, keyboardist Margita Stefanović and bassist Bojan Pečar, with other members mostly remaining for comparatively shorter periods.

Rounding out Katarina II's inaugural lineup were Dušan Dejanović (another former Limunovo Drvo member) on drums and Zoran "Švaba" Radomirović on bass guitar.

The following year, the band took the offer from fellow musician and RTV Ljubljana's musical director Srđan Marjanović of re-recording their debut album material in the state-owned media company's studios.

Mihajlović also ran afoul of the law — a transgression that got him a jail stint — and after serving the punishment got informed by the rest of the band he was no longer a Katarina II member.

Due to constant SFR Yugoslavia-wide touring, with frequent stops in Belgrade, Zagreb and Ljubljana, and occasional TV spots, the band's popularity had gradually grown.

Produced by Vladimir Smolec featuring guest appearances by Massimo Savić as well as Karlowy Wary member and SIM studio co-owner Tomo in der Mühlen, Ekatarina Velika gave the band with its first bona fide hits, "Oči boje meda" ("Honey Colored Eyes"), "Modro i zeleno" ("Indigo and Green") and "Tattoo".

In keeping with the theme of the "Tattoo" track, the album cover arranged by Dušan Gerzić features the band members painted in Native American ritual body art.

With the hits "Budi sam na ulici" ("Be Alone on the Street"), "Ti si sav moj bol" ("You Are All My Anguish"), "Novac u rukama" ("Money in the Hands"), and "Kao da je bilo nekad" ("As If It Had Once Been") came some lukewarm reviews from the critics complaining about the similarities to the works of the Simple Minds.

During spring of the same year, Ivan Ranković decided to leave EKV in order to form a new group Ulica Od Meseca with his old bandmates from Tvrdo Srce i Velike Uši.

Ranković was replaced by the actor Srđan Todorović, a former Disciplina Kičme member, as drummer, playing his first show on 9 April 1987 at the New Rock festival held at the La Locomotive club in Paris.

Prominent tracks from the album include "Zemlja" ("Earth"), "7 Dana" ("7 Days"), "Pored mene" ("Beside Me"), "Ljudi iz gradova" ("People From The Cities"), and "Ljubav" ("Love").

New extensive tour commenced in early 1988, and EKV enlisted help from Tanja Jovićević of Oktobar 1864 and Zvonimir Đukić from Van Gogh to appear as backing live musicians.

The following year, Mladenović participated in the anti-war project Rimtutituki, also featuring Električni Orgazam and Partibrejkers members, releasing the single "Slušaj 'vamo" ("Listen Up").

[2][3] During the middle of 1992 the band toured with the new bassist Dragiša Uskoković "Ćima", with whom they recorded the final studio album Neko nas posmatra (Somebody Is Watching Us), released in May 1993.

The album featured a more accessible and communicative sound especially present in the songs "Ponos" ("Pride"), "Jadransko more" ("The Adriatic Sea"), "Just Let Me Play Some Modern R'n'R Music" and "Zajedno" ("Together").

After the album release, in September of the same year, Ekatarina Velika, Električni Orgazam, Partibrejkers and the Zagreb band Vještice performed in Prague and Berlin on the concerts entitled Ko to tamo pjeva (Who's That Singing Over There).

The two started recording the material partially written in 1985 when, with the guitarist Goran Vejvoda, they had several live appearances under the moniker Dah Anđela (Angel's Breath).

In 1996, she appeared on the Električni Orgazam unplugged live album Živo i akustično (Live and Acoustic), and in 1998, on the fiftieth anniversary of the Universal Declaration of Human Rights signing, she appeared in Pula with Zoran Stojanović, the leader of the Zagreb band Veliki Bijeli Slon, being, along with Rambo Amadeus, the first Serbian musician to play in modern-day Croatia after the Yugoslav Wars.

The Zagreb recordings, made at the Kulušić club, were announced by the rock critic Dražen Vrdoljak and featured Theodore Yanni on guest guitar.

Of the bands heavily influenced by Ekatarina Velika, by far the most notable is Van Gogh,[5][6] which has risen to the status of one of the most popular rock acts in Serbia in the second half of the 1990s.

The band's work was also praised by Yugoslav rock icons like Rambo Amadeus and Dado Topić In 2003, a tribute album to Mladenović entitled Kao da je bilo nekad... Posvećeno Milanu Mladenoviću (Like It Happened Someday...

The album consists of 15 covers of Mladenović's songs (14 EKV and one Šarlo Akrobata song) by a range of musicians, spanning from rock veteran Dado Topić, over EKV contemporaries like Električni Orgazam, Darko Rundek, Partibrejkers, Miško Plavi, Vlada Divljan, Del Arno Band, and Tanja Jovićević, to younger acts, like Jarboli, Darkwood Dub, Novembar, Night Shift, Block Out, and VROOM.

Mladenović's former Šarlo Akrobata bandmate Dušan Kojić also appeared on the album under the pseudonym Crni Zub, participating in the cover of "Zemlja".