В 1966 году карьера Харламова в хоккее вновь была поставлена под угрозу. На этот раз камнем преткновения стал его небольшой рост. Несмотря на то что за короткое время Харламов превратился в одного из лучших игроков Детско-юношеской спортивной школы ЦСКА и стал любимцем Кулагина, главный тренер команды Анатолий Тарасов не видел в нем будущего гения хоккея. Он считал, что с таким ростом никаких перспектив у Харламова нет. Тарасов не уставал повторять: «Все выдающиеся канадские хоккеисты великаны по сравнению с нашими. Как же мы их победим, если наши нападающие карлики, буквально — метр с кепкой?» В итоге в 66-м Харламова отправили во вторую лигу, в армейскую команду Свердловского военного округа — чебаркульскую «Звезду». И там произошло вроде бы чудо, но на самом деле вполне закономерное явление, если исходить из того, что все в судьбе нашего героя уже было предопределено. Перворазрядник Харламов «поставил на уши» весь Чебаркуль, сумев за один сезон забросить в ворота соперников 34 шайбы. Тренер команды тут же сообщил об успехах молодого «варяга» из Москвы Кулагину. Тот сначала, видимо, не поверил. Однако весной 67-го в Калинине Кулагин сам увидел Харламова в деле и понял, что место его в основном составе ЦСКА. Единственное, что смущало, — как отнесется к этому предложению Тарасов.
Говорят, что тот разговор Кулагина с Тарасовым по поводу дальнейшей судьбы талантливого хоккеиста был долгим и тяжелым. Тарасов по-прежнему сомневался в возможностях Харламова, считал его взлет в «Звезде» случайным. Но Кулагин продолжал настаивать на переводе 19-летнего хоккеиста в Москву. И Тарасов сдался. Так летом 67-го Харламов был вызван на тренировочный сбор ЦСКА на южную базу в Кудепсту.
В первенстве страны 1967–1968 годов команда ЦСКА стала чемпионом. Вместе с нею радость победы по праву разделил и Валерий Харламов. Именно тогда на свет родилась знаменитая армейская тройка Михайлов — Петров — Харламов. В декабре того же года ее включили во вторую сборную СССР, которая заменила команду ЧССР на турнире на приз газеты «Известия» (она не приехала в Москву после августовских событий). В 1969 году 20-летний Харламов стал чемпионом мира, установив тем самым рекорд: до него подобного взлета в столь юном возрасте не знал ни один хоккеист Советского Союза.
К началу 70-х Харламов уже безоговорочно считался лучшим хоккеистом не только в Советском Союзе, но и в Европе. Он четырежды становился чемпионом СССР, трижды чемпионом мира и дважды — Европы. На чемпионате СССР в 1971 году он стал лучшим бомбардиром, забросив в ворота соперников 40 шайб. В начале 1972 года в составе сборной СССР он завоевал олимпийское «золото», стал лучшим бомбардиром турнира, забросив 9 шайб. А осенью того же года Харламов покорил и Северную Америку.
Знаменитая серия матчей между хоккейными сборными СССР и Канады стартовала 2 сентября 1972 года на льду монреальского «Форума». Ни один житель североамериканского континента не сомневался тогда в том, что вся серия из восьми игр будет выиграна их соотечественниками с разгромным для советских хоккеистов счетом. Если бы кто-то возразил, его бы назвали сумасшедшим. А что же произошло на самом деле? В первом же матче разгромный счет настиг не нас, а канадцев: 7:3! Для «кленовых листьев» это было шоком. Лучшим игроком в советской команде они безоговорочно признали Харламова, забросившего в матче две шайбы. А ведь, по меркам канадского хоккея, Харламов был «малышом», и соперники особенно сердились, когда именно Харламов раз за разом обыгрывал их, могучих и огромных, на льду. Сразу после игры кто-то из канадских тренеров нашел Валерия и предложил ему миллион долларов за то, чтобы он играл в НХЛ. Харламов тогда отшутился: мол, без Михайлова и Петрова никуда не поеду. Но канадцы не поняли юмора и тут же заявили: мы берем всю вашу «тройку». Естественно, никто никуда не перешел, да и не мог перейти. Не те тогда были времена.
Харламов принадлежал к тому редкому типу людей, которых любили буквально все. Например, он играл в ЦСКА, а эту команду многие болельщики откровенно недолюбливали. Почему? Именно на базе ЦСКА строилась сборная страны, и поэтому спортивное руководство беззастенчиво забирало под армейские стяги лучших игроков из других команд. Однако Харламова, игравшего в ЦСКА, любили все болельщики без исключения. За его игру, за добрый характер. Хотя порой и у него случались досадные срывы. Редко, но случались.