He was born in Kensington in London in 1934. His mother, Noel Margery Collette-Thomas, was the first of Rex Harrison's six wives; they divorced in 1942. Noel was raised together with his nephew Richard Michael Collette Thomas (later a Lt.-Col. who was KIA in France in 1944) during their early years by his grandparents (Major John Cyril Collette Thomas & Jessie Maud Scott-Brown) in Bude, North Cornwall. At age fifteen she took him out of school at Radley to live in the Swiss Alps. He never returned to school and began ski-racing. He joined the Ipswich repertory theatre group and taught himself guitar, but his main interest and most of his spare time was spent skiing. At an early age he was a member of the British ski team, becoming its first giant-slalom champion in 1953, and representing Great Britain at the 1952 Winter Olympics in Oslo, Norway, and at the 1956 Winter Olympics in Cortina d'Ampezzo, Italy.
Harrison undertook National Service and, after leaving the army in the 1950s, toyed with the idea of becoming a journalist, but instead, concentrated on his guitar. His early break came when he took a regular part in the BBC Television programme, Tonight, as part of a team who sang the day's news in a calypso style.
When Harrison was 20, he started playing professionally, around the tables in a Greek restaurant in London. He also made a living playing in bars and nightclubs all over Europe, including appearances at the Blue Angel Night Club, where one show was recorded for a live album.