Осенью 1945 года Куц ушел служить в Балтийский флот: сначала был простым артиллеристом, затем дослужился до командира расчета 12-дюймового орудия. Там же впервые вышел на беговую дорожку во время соревнований в честь Дня Победы. Его победа была настолько впечатляющей, что с этого момента его стали отправлять на все соревнования по бегу, и везде он оказывался победителем. Многие тогда удивлялись его успехам, так как никогда не подозревали в толстяке Куце таких способностей.

Между тем, не имея рядом с собой никакого опытного тренера, Владимир год от года улучшал свои показатели. Например, в беге на 5 тысяч метров он показал результат выше нормы 2-го разряда – 15 минут 44,4 секунды. Лишь весной 1951 года ему посчастливилось встретиться в Сочи с известным тренером по легкой атлетике Леонидом Хоменковым, который специально для Куца составил план тренировок. После этого было участие в ряде соревнований, в большей части из которых Владимир вышел победителем. А зимой 1954 года судьба свела его с тренером Григорием Никифоровым, который взялся за него всерьез. С этого момента Куц стал планомерно тренироваться под его руководством.

Сезон 1953 года был очень успешным для спортсмена, который еще весной пребывал в безвестности: две серебряные медали на IV фестивале молодежи в Бухаресте, две золотые на первенстве страны, всесоюзный рекорд к концу сезона.

В 1954 году спортсмен одержал первую крупную победу, установив мировой рекорд на чемпионате Европы в Берне, после чего стал одним из фаворитов предстоящих в Австралии XVI Олимпийских игр.

Олимпийские игры начались 22 ноября 1956 года. Однако за три дня до их открытия с Куцем случился инцидент, который едва не оставил его за бортом этих соревнований.

Куц был заядлым автолюбителем и незадолго до Олимпиады купил себе «Победу». Но, видимо, вдоволь наездиться на ней не успел, поэтому, едва прибыв в Мельбурн, решил наверстать упущенное на чужой земле. Он уговорил одного австралийца дать ему прокатиться на его машине в пределах олимпийской деревни. Тот согласился. Владимир усадил в нее тренера Никифорова, своего коллегу Климова и сел за руль. А далее произошло неожиданное. Видимо, не рассчитав свои действия (машина была иностранная, руль с правой стороны, а ее двигатель был в два раза мощнее, чем у «Победы»), Куц рванул автомобиль с места и врезался в столб. В этой аварии он получил дюжину различных ран, которые пришлось залечивать в местном травмпункте. Это событие, естественно, не укрылось от глаз вездесущих репортеров, и уже вечером того же дня газеты трубили о том, что надежда советских спортсменов Владимир Куц тяжело травмирован и выбывает из игры. Чтобы опровергнуть эти слухи, Куцу пришлось лично явиться на танцы в олимпийский концертный зал и на танцевальной площадке продемонстрировать всем, что он абсолютно здоров.

Первое выступление Куца на Олимпиаде (забег на 10 000 метров) состоялось 23 ноября. В этом забеге участвовали четырнадцать спортсменов, но бесспорными фаворитами были двое: Куц и англичанин Гордон Пири. Большинство специалистов отдавали свое предпочтение англичанину, который незадолго до Олимпиады в очном поединке не только обыграл Куца на дистанции 5000 метров, но и отобрал у него мировой рекорд. Но на этот раз все получилось иначе. Как пишет Е. Чен:

«Только сами спортсмены и настоящие специалисты знают, как тяжело во время долгого, изнурительного стайерского бега совершать даже короткие ускорения. А в Мельбурне Куц предложил неотступно следующему за ним Пири целых три таких рывка по 400 метров каждый. Это был действительно бег на грани жизни и смерти. И после третьего рывка, хотя до финиша осталось только около полутора километров, Пири сдался.