Первым педагогом Кати стала Л.И. Рафаилова, затем мастерство талантливой ученицы оттачивала Елизавета Павловна Гердт – замечательная балерина Мариинского театра. Она привила ученице не только безупречный классический стиль, но и артистизм, тонкую культуру интонирования движений, научила личностному переживанию музыки. Стоит ли говорить, сколько душевных и физических сил требовала учеба? Но темперамент хрупкой и нежной девочки вылился в колоссальный балетный талант. Максимова очень рано стала знаменитой: ученица второго класса так ярко выступила в маленькой роли Белочки в детской опере «Морозко», поставленной на сцене Большого театра, что привлекла внимание зрителей и критиков – ее игру даже отмечали в рецензиях на премьеру. Еще в училище балетмейстеры ставили номера специально для Максимовой: в 7-м классе Катя исполнила номер В.А. Варковицкого «Соловей» на музыку А.А. Алябьева, сам великий К.Я. Голейзовский поставил для нее и И. Хмельницкого «Романс» на музыку С.В. Рахманинова. Тогда же ей доверили настоящую «балеринскую» партию – роль Маши в балете П.И. Чайковского «Щелкунчик» в постановке В.И. Вайнонена. Именно с этой ролью она завоевала свою первую золотую медаль на Всесоюзном конкурсе артистов балета в 1957 году. Как лучшая ученица, Екатерина танцевала в школьном концерте в честь посещения училища королевой Бельгии Елизаветой, а когда в Москве проходили первые гастроли французской Гранд-опера, именно ее Харальд Ландер выбрал для показа своих принципов построения классического урока.
В 1958 г. Максимова успешно окончила МХУ и сразу была принята солисткой в балетную труппу Большого театра. С первого же сезона Екатерине доверили сольные партии в классических спектаклях, а новый балетмейстер Ю.Н. Григорович предложил главную роль в московской премьере балета С.С. Прокофьева «Каменный цветок» – самой новаторской постановке в советском балетном театре того времени. С первого своего появления – и навсегда – Максимова стала настоящей любимицей публики. В том же году она выезжала вместе с театром на гастроли в Америку, где сразу очаровала зрителей, а восхищенная пресса назвала ее «чудесным маленьким эльфом», «бэби Большого балета». Пришло признание, но это ни в коей мере не отменило ежедневных репетиций и не погасило желания совершенствовать свое мастерство. Именно поэтому в 1960 г. Максимова становится первой ученицей Галины Улановой. По словам самой Екатерины, сила художественного и человеческого влияния великой балерины на нее была беспредельна. Благодаря своему педагогу она стала самой юной исполнительницей партии Жизели. Исполнение Максимовой этой сложной и в техническом, и в актерском отношении роли безоговорочно признали даже самые строгие критики.
Присутствие у исполнительницы интеллекта и иронии наполняет ее танцы искрящимся юмором, изысканным шармом, некоторым эксцентризмом. Редкая красота, классические пропорции фигуры, красивая форма ног, природный дар грации и безграничное обаяние, потрясающая женственность, истинный артистизм в сочетании с легкостью и элегантной непринужденностью при исполнении сложнейших па – таким стал сценический облик Максимовой. А еще на лице принцессы балета играла загадочная улыбка и лучились глаза с искорками.
Репертуар балерины с первых лет работы в театре был обширен и разнообразен, и каждый сезон пополнялся новыми партиями в классических и современных спектаклях: Сильфида («Шопениана»), Водяница («Конек-Горбунок»), Лиззи («Тропою грома»), Коломбина («Медный всадник», все в 1960 г.); Жанна («Пламя Парижа»), Мавка («Лесная песня», обе в 1961 г.); Мария («Бахчисарайский фонтан»), Муза («Паганини»), Маша («Щелкунчик»), Нимфа («Спартак» в постановки Л.В. Якобсона, все в 1962 г.) и др. Максимова стала первой исполнительницей партий Солистки в «Класс-концерте» А.М. Мессерера, принцессы Флорины в новой редакции Ю.Н. Григоровича балета «Спящая красавица»; Золушки (постановка Р.В. Захарова), принцессы Авроры («Спящая красавица»), Балерины в «Петрушке» (постановка М.М. Фокина, редакция К.Ф. Боярского).
К 1965 году Екатерина, завоевавшая титул идеальной лирической балерины, потрясла публику бравурной партией Китри в балете Минкуса «Дон Кихот». Да и критика пришла в восторг от виртуозного мастерства и ярко выраженного комедийного дарования Максимовой. Ее исполнение Китри до сих пор остается непревзойденным эталоном для этой роли. И как только искусствоведы написали: «Что бы ни танцевала Максимова – музыка, солнце, жизнь дышат в каждом ее движении» (Е. Луцкая), она тут же опровергла только что сложившийся стереотип – за искрометной Китри последовали удивительная, ни на кого из предшественниц не похожая Одетта-Одиллия («Лебединое озеро», 1968), а затем трагическая, истинно шекспировская юная Джульетта («Ромео и Джульетта» в постановке Л.М. Лавровского, 1973).