1990-я гады

Музычная кар'ера Караліны пачалася ў 1991 годзе з удзелу ў папулярным у краіне конкурсе «Макфест 91», які праходзіў у горадзе Штып. На конкурсе юная Караліна, якой тады было ўсяго 11 гадоў выканала песню «Мамо, пушце ма» (Мама, адпусці мяне), якая пазней стала хітом і дала назву дэбютнаму альбому спявачкі, што выйшаў у 1992 годзе. Караліна часта бярэ ўдзел у галоўным музычным фэсце Македоніі — «Скопје-Фест». У 1994 годзе яна дэбютавала на ім з песняй «Кој да ти каже» (Хто табе скажа), у 1996 годзе з песняй «Ма, ајде паказвай ми» (Давай, скажы мне) заняла дзявятае месца, а ў 1998 годзе — высокае чацвёртае месца з песняй «Украдени ноќи» (Выкрадзеныя ночы), за якую прагаласавалі 10 454 македонцаў.

2000—2001 гады

Пасля такога поспеху, вядомы македонскі лэйбл Avalon Productions падпісвае кантракт на запіс дэбютнага сталага альбома Караліны Гочавай, які ўбачыў свет у 2000 годзе. Альбом, што атрымаў назву «Јас імам песні» (У мяне ёсць песня), утрымваў адразу некалькі хітоў «Сакај ма» (Кахай мяне), «Без оглед на з?» (Нягледзячы на ўсё) і «Немир» (Турбота), які яна выканала ў дуэце з Тошэ Проескім. Каб замацаваць поспех альбома, Караліна зноў бярэ ўдзел у фэсце «Скопје-Фаст», на якім песня «За нас» займае другое месца.

2002 год

На хвалі поспеху ў 2002 годзе, выходзіць другі сталы альбом Караліны Гочавай «Зошто санат има крај» (Чаму сны сканчаюцца). У гэтым жа годзе Караліна робіцца папулярнай на тэрыторыі краін былой Югаславіі дзякуючы выступу на фестывалі «Suncane Skale» ў Чарнагорыі з песняй «Кажи ми» (Скажы мне). У 2002 Гочава выйграла «Скопје-Фест 2002» з песняй «Од нас зависи» (Гэта залежыць ад нас). Перамога на фэсце дала магчымасць Караліне паехаць у Талін, каб прадстаўляць сваю краіну на конкурсе песні Еўрабачанне 2002. На конкурсе Караліна выступіла не вельмі ўдала, стаўшы 19-й з 24-х удзельнікаў і атрымаўшы ўсяго 25 балаў. Выступ Караліны ацанілі толькі 5 краін:

• Румынія — 12 балаў
• Мальта — 5 балаў
• Харватыя — 4 балы
• Кіпр — 3 балы
• Фінляндыя — 1 бал

2003 год

У 2003 годзе Караліна Гочава выпусціла свой трэці альбом «Знаеш колку вредам» (Ты ведаеш чаго я каштую). Гэты альбом стаў вельмі папулярны не толькі ў Македоніі, але і ў іншых краінах былой Югаславіі. Усё гэта прывяло да таго, што выходзіць яе альбом на сербскай мове, які атрымаў назву «Кад звезде нам се склопе… као некада» (Калі зоркі выстраіліся ў шэраг, як некалі). Альбом улучаў усе песні трэцяга альбома, але з адаптаваным пад сербскую мову тэкстам.