Karolina Gočeva nació en Bitola, Antigua República Yugoslava de Macedonia, el 28 de abril de 1980. Su interés por la música apareció desde muy joven, siendo su intervención con 10 años en el festival infantil Si-Do su primera actuación pública. Un año más tarde, en 1991, actuó en el festival anual Makfest en la localidad de Štip cantando Mamo, pušti me. Estos festivales, en los que ganó en casi todos al menos uno de los premios, marcaron el inicio de su carrera. Cuando tenía catorce años ganó el premio a Mejor artista femenina en los Velicenstveni (equivalentes a los Grammy macedonios). Ese mismo año 1994, debutó con la canción Koj da ti kaže en uno de los eventos musicales más importantes del país, el Skopje Fest. A partir de 1996, el festival empezó a ser usado como preselección macedonia para Eurovisión y, en cierto modo, fue entonces cuando empezó el periplo eurovisivo de la cantante. Aquel año quedó novena con la canción Ma ajde kaži mi y dos años más tarde obtuvo una mejor posición, alcanzando el cuarto puesto con la canción Ukradeni nokji.

En el año 2000, Karolina firmó contrato con la discográfica Avalon Productions y produjo su primer álbum de estudio: Jas imam pesna. De él se desprenden varios sencillos como Sakaj me, Bez ogled na se y Nemir, esta última canción a dúo con el ulterior eurovisivo Toše Proeski. Consiguió ser uno de los tres álbumes más vendidos del año. Con su primer disco lanzado recientemente, lo volvió a intentar en la preselección macedonia interpretando Za nas, escrita por Darko Dimitrov, pero consiguió el segundo puesto, tan solo superada por el grupo de chicas XXL. Tras promocionarse a través de conciertos y festivales y adquirir mayor popularidad, consiguió publicar en 2002 su segundo álbum, Zošto sonot ima kraj, con los sencillos Ti možes y Kje bide se vo red y algunas versiones en inglés. En abril de 2002 logró llenar el Universal Hall de Skopje durante 3 días consecutivos. También se presentó al festival Sunčane Skale con la canción Kaži mi.

Debido a toda esta popularidad, por fin logró ganar el tan ansiado Skopje Fest y representar a su país en el Festival de Eurovisión celebrado en Estonia. Con la canción Od nas zavisi terminó en un paupérrimo decimonoveno lugar. Aún con todo, su participación no estuvo exenta de polémica debido al idioma utilizado, ya que ella y su discográfica preferían competir en inglés pero la MKTV les obligaba a realizar la actuación en macedonio. De hecho, llegó a haber amenazas por parte de la cadena pública de llevar a Andrijana Janevska, segunda clasificada del Skopje Fest de aquel año, si Karolina no cedía. Finalmente Karolina dio su brazo a torcer y tuvo que cantar enteramente en macedonio, pese a que el título estaba en inglés.

En marzo de 2003 salió a la venta su tercer disco, Znaeš kolku vredam, nuevamente con sus respectivos sencillos acompañados de sus correspondientes videoclips: Hipokrit, Ljubov pod oblacite y Srescemo se opet. A partir de ese año, Karolina amplió fronteras y extendió su carrera musical y la venta de sus álbumes a todos los demás países ex yugoslavos. Incluso llegó a grabar otra vez su tercer álbum íntegramente en serbio, pero esta vez bajo el título Kad zvezde nam se sklope… kao nekada (Cuando las estrellas se alineen… como antes). Una segunda incursión en el festival Sunčane Skale tres años después de su primera intervención le otorgó una cuarta posición con la canción Ruža Ružica, la cual se convirtió en un éxito arrollador. La eurovisiva Kaliopi le escribió la canción Se lazam sebe, que sería su siguiente hit. En su cuarto álbum, Vo zaborav (y su respectiva versión serbia, U zaboravu), participaron numerosos compositores de renombre como Vlatko Stefanovski, Bajaga, Ivica Brcioski o el también eurovisivo Dino Merlin. Tal fue su éxito, que alcanzó las 20.000 copias vendidas. En 2007 grabó un dueto con el popular grupo serbio Flamingosi, titulado Ti i ja. Su incursión en el mercado serbio estaba afianzándose.

En 2007 decidió volver a representar a su país en el Festival de Eurovision, así que se presentó al Macedonian Eurosong con la canción Mojot svet, competición que ganó y gracias a la cual se convirtió en la primera macedonia en representar a su país dos veces. Actuó en el escenario de Helsinki logrando pasar de la semifinal junto a otros nueve países y en la final consiguió la decimocuarta posición.

Tras su segunda aparición en Eurovision también participó en el Radijski Festival con la canción Kad te nema y quedó en segunda posición, aunque ganó el premio a Mejor composición. Lanzó un disco de título homónimo a su canción eurovisiva (con su correspondiente versión inglesa, My world) y en 2008 lanzó un álbum con toques del folclore tradicional macedonio, Makedonsko devojče, en colaboración con el compositor Zlatko Origanski. Dicho álbum se convirtió en el más vendido de 2008 y el sencillo con el que se dio a conocer fue Ptico malečka. La discográfica City Records se encargó de exportar el álbum a otros países también ex yugoslavos.

Su fama en Serbia ya se había hecho tan patente que hizo una colaboración con la estrella de R&B y hip-hop Wikluh Sky. Su canción Kraj, presentada en la gala inicial del Gran Hermano serbio, alcanzó de nuevo los números uno no solo de las listas de ventas de Serbia y Macedonia, sino de otros países. El álbum en el que se incluyó la canción llevó por título el mismo nombre y fue editado a principios de 2010. La poderosa balada Za godina, dve fue elegida para ser el segundo single. Sus últimos trabajos son los álbumes Kapka pod neboto (de 2010) y Najubavi pesni (de 2012). A finales de 2014 lanzó Makedonsko devojče 2, la segunda parte de su exitoso álbum de 2008. En 2018 editó su último disco Izvor.

Fuera del ambiente musical, Karolina Goceva logró ser la cara visible de la campaña publicitaria en toda ex Yugoslavia de productos para el pelo H&S en 2004, así como de la marca KARA a principios de 2005.