У Виктора Клименко необычная судьба. Его отца — Савву Ивановича, бывшего кубанского казака, в 30-е раскулачили и сослали в Карелию. С началом Второй мировой войны после наступления финской армии деревня, в которой жили ссыльные, оказалась за линией фронта. Поэтому первые годы жизни маленький Витя провел в лагере для интернированных. Никаких воспоминаний об этом у него не сохранилось. Может быть, оно и к лучшему. Но после окончания войны семья (мать тоже была из ссыльных) приняла вполне предсказуемое решение не возвращаться в СССР.

В детстве Виктору приходилось сталкиваться и с нацинализмом — Финляндия выступала в войне на стороне Германии, а потому в маленьком мальчике, только начинавшем осваивать русский язык сверстники видели врага, дело нередко доходило до драк — и с нуждой, работать пришлось с детства. Но очень скоро в Викторе обнаружились артистические способности. Особенно ему нравилось петь. 

Уже к началу 60-х он стал довольно известным в стране певцом. И даже выиграл национальный песенный конкурс. Правда, ни там, ни позже на "Евровидении" в Неаполе никто так и не узнал, что гражданином Финляндии Виктор Клименко не был.