L’argent trois fois, suivi de l’or
Elle participe à ses premiers Championnats du monde en 2003 où elle remporte une médaille d'argent dans l'épreuve par équipes le jour de ses seize ans. Elle décroche ensuite deux autres médailles d'argent, à la poutre et aux exercices au sol. En mai 2004, elle s'adjuge l'or dans les trois épreuves aux championnats d'Europe.
La marge la plus importante
Trois mois plus tard, aux Jeux de la XXVIIIe Olympiade à Athènes en 2004, Catalina mène son pays à la victoire dans l'épreuve par équipes. Elle se qualifie également pour deux finales aux agrès six jours plus tard. À la poutre, elle devance Carly Patterson des États-Unis (9.787 contre 9.775) et décroche sa deuxième médaille d'or. Après une pause de seulement 45 minutes, la Roumaine remporte la finale des exercices au sol. Sa marge de victoire, .188 points, est la plus importante de toute l'histoire de cette épreuve.