Катерина Гелебешева-Костадиновска е родена во Скопје на 16.03.1969 година. Во нижото музичко училиште била примена на својата 5 – годишна возраст учејќи пијано во класата на проф. Евушка Трпкова – Елезовиќ, кај која продолжила и во средното музичко училиште. Во нејзиното образование по пијано во средното музичко училиште учела и во класата на проф. Тодор Светиев. На Музичката Академија во Загреб се запишала во 1987 година во класата на истакнатиот пијанист и педагог проф. Владимир Крпан. Дипломирала како најдобар студент во 1991 година, здобивајќи се со звањето академски музичар, пијанист и професор по пијано.
На Факултетот за музичка уметност во Скопје постдипломските студии ги завршила во 1993 година, во класата на проф. Борис Романов.
Во текот на нејзиниот средношколски и факултетски едукативен период редовно учествувала на голем број јавни часови, на аудиции, а настапувала честопати и на концерти, додека од 1980 година станала редовен учесник на сите натпревари на ученици и студенти по музика, секогаш освојувајќи високи места како во Републиката, така и надвор од нејзините граници и тоа први, втори и специјални награди.
Една година пред нејзиното запишување на Музичката академија во Загреб (1986) станала добитник на специјалното меѓународно признание за изведба на дела од Борис Папандопуло, во Грожњан каде што била воедно и најдобар млад учесник. За еден од нејзините најголеми успеси се смета освоената III-та награда на XXIV-от натпревар на млади музички уметници во Загреб одржан во 1990 година. Била и успешен преставник на Загребската Музичка академија на двете средби на студентите од Музичките академии од поранешната Југословенска држава, што се одржале во Љубљана (1989) и Приштина(1990).
Во циклусот концерти Подиум на млади на фестивалите Скопско лето и Охридско лето настапила по четирипати во периодот од 1987 година до 1997 година.
Како учесник земала учество на многубројни пијано семинари под раководство на Р.Керер, И.Ендо, Е.Тимакин, Р.Мураро, М.Н.Гинзбург и др. Нејзината солистичка кариера како пијанист ја одбележуваат голем број концерти ширум Македонија, како и во Загреб, Сараево, Дубровник, Грожњан, во Италија (Стрезе), Турција (Истанбул), Бугарија (Софија), Португалија (Порто), Србија (Ниш, Белград, Нови Сад), Холандија (Харлем, Ден Бош), Романија (Букурешт, Крајова), Франција (Париз),..
Покрај самостојните концертни настапи, со посебен успех и високи оценки од музичката критика, повеќекратно настапувала, до сега, со Македонската филхармонија, Камерниот оркестар при МФ, Загребската филхармонија, Симфонискиот оркестар на ХРТВ Загреб. Од големиот број нејзини настапи за одбележување е изведбата на клавирскиот концерт од Камиј Сен-Санс под диригенство на маестро Ангел Шурев.
Во 2000-та година заедно со нејзиниот сопруг Глигор Гелебешев реализира активна уметничка кариера како пијано дуо, а од 2002-та година остварува и успешна уметничка соработка со обоистот Васил Атанасов.
Веднаш по нејзиното дипломирање во 1991 година се вработила како професор по пијано во МБУЦ "Илија Николовски Луј" во Скопје каде останала до 1995 година. За време на овој период нејзината успешна педагошка работа ја потврдиле и нејзините ученици со учество на тематските вечери и завршни концерти организирани од ова училиште. Од октомври 1995 година работела како доцент по пијано на одделите I,II,VI и VII, а од 2004 година работи и со студент на III оддел - одделот по пијано .
Од 2005 година работи како вонреден професор по пијано на Факултетот за Музичка уметност во Скопје, но исто така предава и камерна музика и корепетиција на катедрата по пијано.
Покрај нејзината активност на сцената како самостоен солист, често зема учество и како пијанист-соработник. Од 2002-та година активно соработува со обоистот Васил Атанасов, со кого има реализирано над 30 концерти низ Македонија (Скопје, Куманово, Струмица, Гевгелија, Неготино, Охрид...), како и на сите значајни фестивали како Охридско лето, Скопско лето, Битола-Хераклејски вечери,Штипско лето. ДММ, Есенски музички свечености.Имаат издадено и ЦД со наслов Романтична музика (2006) со дела од Паскули, Даили, Рахмањинов, Понкиели, Колин, Карапатозо, Ибер и Десландре.За музичката архива на МРТВ направиле повеќе трајни тонски снимки.
Особено акцентирана концертна дејност од 2001 година па се до денес остварува со пијано дуото Гелебешеви, кое го формирала со нејзиниот сопруг Глигор Гелебешев. Во концертната актива на пијано дуото влегуваат над 40 јавни настапи во скоро сите градови низ Македонија (Скопје, Битола, Прилеп, Штип, Охрид, Куманово, Тетово, Струмица, Гевгелија...), кои музичката критика ги оценува со најпофални зборови. На идентичен прием наидуваат и концертите остварени и на скоро сите најзначајни фестивали во државата (Охридско лето, Скопско лето, Битолско лето, Прилепско лето, Интерфест-Битола, Златна лира, ДММ. Пијано дуото Гелебешеви настапува и во странство- 2005 година настап во Париз (Франција); 2007 година настап во Нови Сад (Србија); 2008 година настап во Букурешт, Крајова (Романија); 2009 година настап во Ниш (Србија) и 2009 година настап во Харлем, Ден Бош (Холандија).
Во 2008 година го имаат издадено и првото ЦД со дела од Дебиси, Хачатурјан, Шопен, Шабрие и Барток. Како пијано дуо за МРТВ оствариле и повеќе трајни тонски снимки.