После выхода альбома между Младеновичем и Михайловичем случился скандал и разлад. Более того, Михайлович оказался в тюрьме из-за проблем с законом. После освобождения он был проинформирован о своём исключении из группы, однако он закрепил за собой все права на название «Катарина II». Музыканты вынужден были сменить название коллектива на «Екатарина Велика», выбранное в честь императрицы России Екатерины II Алексеевны. Впоследствии участниками ещё использовалась и аббревиатура ЕКВ. После этого группу покинул ещё один музыкант, на этот раз Иван Вдович. Причиной ухода стали проблемы с наркотиками. Вместо него в группу пришёл Иван «Фирчи» Феце.

1985: Екатарина Велика

Популярность группы возрастала после гастролей в стране. Группа давала концерты в Белграде, Загребе и Любляне. В 1985 году группа записала второй альбом «Екатарина Велика» в загребский студии «SIM studio». В записи приняли участие Милан, Маргита, Боян и Феце, продюсировал альбом Владимир Смолец. В композициях преобладали быстрые и энергичные ритмы. На обложке альбома участники были изображены в образе американских индейцев.

Известными песнями стали «Очи боје меда» (Глаза медового цвета), «Tattoo» (Татуировка) и «Модро и зелено» (Синий и зелёный). 22 марта 1985 группа впервые отправилась за границу, выступив на фестивале «Дни культуры» в итальянском Турине. В Загребе на фестивале «Боље вас нашли» группа дала ещё один концерт.

В конце 1985 года Иван Феце отправился служить в армию, а его заменил ещё один барабанщик Иван «Рака» Ранкович.

1986: С' ветром уз лице

В 1986 году «Екатарина Велика» выпустила третий альбом «С' ветром уз лице» (Против ветра), который стал прорывом для команды и возвёл её в ранг звёзд. Продюсированием занимались Драга Чачинович, Милан Младенович и Маргита Стефанович. На композициях в альбоме уже преобладали оттенки синти-попа: 8-битный семплер E-MU Emulator II и драм-машины. Среди песен выделяются «Буди сам на улици» (Буду сам на улице), «Као да је било некад» (Когда-то было), «Ти си сав мој бол» (Ты боль моя) и «Новац у рукама» (Гроши в руках).

Критики отметили доступность альбома и простые аранжировки вкупе с лёгкими мелодиями. Благодаря этому альбому группа стала выступать на каждом музыкальном концерте. А 2 ноября 1986 в клубе «Kulusic club» был записан концертный альбом «19LIVE!86», вышедший через год. В Белграде группа завершила свои гастроли концертом в Молодёжном центре. Весною Ивана Ранковича сменил новый барабанщик Срджан Тодорович.

1987: Љубав

Во второй половине 1987 года вышел четвёртый альбом группы «Љубав» (Любовь), который считается лучшим альбомом группы и лучшим рок-релизом в Югославии. Перед выпуском пластинки вышел промо-сингл «Земља»/«Први и Последни Дан» (Земля/Первый и последний день). «Екатарина Велика» стала ориентироваться чаще на гитарные соло после прихода австрийского продюсера Теодора Янни. Также фанаты оценили оформление альбома, на обложке которой изображена сама Маргита Стефанович. В оформлении обложки принимал участие художник Вук Видор.

Самыми популярными песнями стали «Земља» (Земля), «Поред мене» (Кроме меня), «Љубав» (Любовь), «7 дана» (7 дней и «Људи из градова» (Люди из города). На пластинке есть и представитель депрессивной лирики — песня «Тонемо» (Раковина).

Группа подтвердила свой звёздный статус, выступив на арене «Pionir» в Белграде. В начале 1988 года началось новое турне совместно с новыми музыкантами: Таней Йовичевич и Дзвинко Дукачем. Вскоре Феце вернулся из армии и на несколько месяцев стал членом «Екатарины Великой», заменив Тодоровича, но в мае 1988 года покинул страну и уехал в Нью-Йорк. Тодорович снова вернулся в группу.