Paul Nicholas was born Paul Oscar Beuselinck on 3 December 1944 in Peterborough. His paternal grandfather, Oscar Beuselinck, was Belgian and had been a chef in the merchant navy during World War II, before becoming head chef on the Union-Castle Line ships between the United Kingdom and South Africa. His maternal grandfather was a London docker.
Nicholas' father, Oscar Beuselinck, a former MI6 agent, became a highly esteemed entertainment and show business solicitor. The family spent holidays at his maternal grandparents' home on the Isle of Sheppey, until Nicholas was 10. After his parents divorced when he was 12, his father's family home was at Letchmore Heath, Hertfordshire, opposite the Bhaktivedanta Manor. His paternal grandparents, Winnie and Oscar, lived in a small cottage on the grounds.
Nicholas began his pop career as early as 1960. Adopting the stage name Paul Dean, he formed Paul Dean & The Dreamers who were booked to support The Savages, the backing band for the British rocker Screaming Lord Sutch.
It was here that Sutch first noticed the young Nicholas, who was soon to become vocalist and pianist with The Savages. Still using the name Paul Dean, he released two solo singles in 1965–66. After taking a new stage name, Oscar, he began a long association with the Australian-born entrepreneur, Robert Stigwood. In 1966, Nicholas signed with Stigwood's Reaction Records label and his first single under his new name, "Club of Lights", scraped into the lower reaches of the Radio London Fab Forty chart.
The second Oscar single was a version of a Pete Townshend song "Join My Gang", which The Who never recorded. His third single, a novelty song called "Over the Wall We Go" (1967) is notable for being written and produced by a young David Bowie. After settling on the stage name Paul Nicholas, he found success in the UK in musicals, beginning with the leading role of Claude in Hair (which Stigwood produced) before winning the title role in the original London production of Jesus Christ Superstar. The part of Danny to Elaine Paige's Sandy made them the first British couple to play the leads in Grease. He joined The Young Vic under Frank Dunlop and played Claudio in Much Ado About Nothing and appeared in Crete and Sgt. Pepper by John Antrobus. He appeared as the Bully of the Boulevard in Richard O’Brien’s T-Zee at London's Royal Court Theatre. He performed in Prospect Theatre Company's Carl Davies musical Pilgrim. While touring with O'Brien in Hair in 1970 he first heard songs from the yet to be produced Rocky Horror Show and made the first professional recording with O'Brien singing "That Ain't No Crime". On the b-side was a song entitled "Very 50s", where O'Brien introduces the characters Brad, Janet, and Dr. Scott.