Костадинка Николова е родена във Варна и завършва Държавната музикална академия "П. Владигеров" в София през 1990 година. В началото на своята кариера, от 1989 до 1992 година, тя е солистка, след което преминава към операта.

През същата година, когато завършва академията, Николова получава признание като лауреат на конкурса за млади оперни певци "Б. Христов" в София.

Тя е изпълнила множество роли в различни опери, включително Норина от "Дон Паскуале" на Доницети, Розина от "Севилският бръснар" на Росини, Церлина от "Дон Жуан", Г-ца Зилберкланг от "Театралният директор", Памина от "Вълшебната флейта", Констанца от "Отвличане от сарая", Деспина от "Така правят всички" на Моцарт, Микаела от "Кармен", Лейла от "Ловци на бисери" на Бизе, Джилда от "Риголето", Жрица от "Аида", Елизабет от "Дон Карлос" на Верди, Мими от "Бохеми", Лиу от "Турандот" на Пучини, и Адела от "Прилепът" на Й. Щраус.

Костадинка Николова има записи с Московското радио и Българското национално радио, и е гостувала в различни страни, включително Германия, Испания, Гърция, Кипър, Русия, и Литва.