Так Олег стал заниматься в секции фигурного катания. На тренировки иногда приходил и сам Панин-Коломенкин. Олега он хвалил, но всегда подчеркивал, что фигурное катание — это прежде всего тяжелый труд. Однако Олег и без напоминаний всегда отличался трудолюбием. Поэтому пришли и первые успехи. В 1948 году, когда ему было шестнадцать, Олег разделил третье-четвертое места на всесоюзном юношеском первенстве, а через два года стал вторым. Но в 1951 году Олега призвали в военно-морской флот.
В конце зимы 1952 года, когда Протопопова перевели на службу в родной город, в часы увольнений он стал появляться на стадионе «Динамо». Опытный специалист, экс-чемпион страны в парном катании Александр Борисович Гандельсман, посоветовал Олегу тренироваться в паре с Маргаритой Богоявленской. На первенстве СССР 1953 года Олег и Маргарита заняли третье место. Правда, и выступающих пар было всего… три. Однако на командиров Олега его успех произвел большое впечатление, и ему разрешили чаще бывать на тренировках. Однажды даже и вовсе отпустили в Москву на сборы фигуристов.
Там, на катке в детском парке Дзержинского района, Олег случайно встретился с десятиклассницей Людой Белоусовой, которая была младше его на три года. Фигурным катанием Белоусова увлеклась после того, как посмотрела «Серенаду солнечной долины» с великой Соней Хени. К тому моменту, когда она увидела на катке Олега, Людмила успела стать перворазрядницей. Вместе они выполнили пробный пируэт. Все удивились, насколько легко и изящно это получилось, и даже зааплодировали. Олегу этот эпизод надолго запомнился.
Вскоре ему пришлось вернуться в Ленинград, а Людмила жила в Москве. Но, оказалось, она тоже запомнила встречу с Олегом. Окончив школу, решила поступать в Ленинградский институт инженеров железнодорожного транспорта. Жила в студенческом общежитии и тренировалась в паре с Олегом Протопоповым. Занимались… в церкви на набережной Лейтенанта Шмидта. Долгое время она служила складам, а в конце 1950-х годов в ней был оборудован первый в Ленинграде искусственный каток.
Так началось их совместное творчество на льду. И поступательное движение к успеху. В 1956 году Белоусова и Протопопов заняли на чемпионате страны четвертое место в парном катании. Уже тогда зрителей поражало, как точно они подбирают к своим выступлениям классическую музыку. Белоусова и Протопопов создавали композиции, не-отъемлемой частью которых были Шопен, Чайковский, Бетховен…
В 1957 году Белоусова и Протопопов заняли уже второе место на чемпионате СССР. Выше их оказались Нина и Станислав Жук. На третьем месте были Майя Беленькая и Игорь Москвин, тоже из Ленинграда. Впоследствии Москвин стал тренером Белоусовой и Протопопова. В этом году произошли перемены и в личной жизни: Белоусова и Протопопов стали мужем и женой.
Через год пара Белоусова и Протопопов вновь заняли второе место на первенстве страны и впервые попробовали себя на международной арене. На чемпионате Европы в Братиславе оказались девятыми, на чемпионате мира в Париже — тринадцатыми. В 1960 года Людмила и Олег заняли уже четвертое место на чемпионате Европы в немецком Гармиш-Партенкирхене. Здесь они впервые показали свои «Грезы любви» и еще трижды повторяли выступление по просьбе восторженных зрителей. В том же году пара впервые поехала на VIII зимнюю Олимпиаду в Скво-Вэлли. Дебютанты Белоусова и Протопопов заняли девятое место. Нина и Станислав Жук оказались шестыми.
Первой золотой наградой Людмилы и Олега стали медали, завоеванные в 1961 году на II Спартакиаде народов РСФСР в Свердловске. После этого Белоусова и Протопопов шесть раз выигрывали чемпионаты страны.
Триумфальным оказалось выступление Белоусовой и Протопопова на IX зимних Олимпийских играх 1964 года в Инсбруке. Победу многие предсказывали двукратным чемпионами мира и шестикратным чемпионам Европы Марике Килиус и Гансу Боймлеру из Германии. Даже жребий, казалось, был на их стороне — они выступали позже Белоусовой и Протопопова. Но то, что показали Людмила и Олег, было подобно чуду. В их выступлении слились воедино музыка и движения, казалось, они сочиняют свой танец прямо на льду.
Золотые олимпийские медали Белоусовой и Протопопова стали сенсацией Олимпиады. «Русские фигуристы открыли новую эру в этом виде спорта», — писала одна из швейцарских газет. Затем последовала серия из четырех блестящих побед на чемпионатах мира и Европы. Она продолжалась с 1965 по 1968 год. И попутно создавалась новая олимпийская программа с музыкой «Лунной сонаты» и Пятой симфонии Бетховена, с музыкой Рахманинова.
На X зимних Олимпийских играх 1968 года во французском Гренобле Белоусова и Протопопов вновь были первыми. Они показали великолепную обязательную программу, не допустив ни единой ошибки, а три дня спустя восхитительную произвольную программу, которой стоя аплодировали 12 тысяч зрителей.