The New Vaudeville Band was a group created by songwriter Geoff Stephens (born 1 October 1934, New Southgate, North London) in 1966 to record his novelty composition "Winchester Cathedral", a song inspired by the dance bands of the 1920s and a Rudy Vallee megaphone style vocal. To his surprise, the song became a transatlantic hit that autumn, reaching the Top 10 in the UK and rising to #1 in the US. The record sold over three million copies worldwide, earning the RIAA certification of gold disc status. The track also won a Grammy Award for Best Contemporary Song in 1967. The lead vocal was sung by John Carter, formerly of The Ivy League, who had sung on the demo of the record, which Stephens decided to keep for the commercial release. An initial long-playing album was also issued in late 1966 by Fontana Records, also titled Winchester Cathedral.

When Stephens received several requests for The New Vaudeville Band to tour, he had to put together a group, as the song was recorded by session musicians hired only for the recording session. He contacted a real group, the Bonzo Dog Doo-Dah Band, which played similar music at the time. Only Bob Kerr from that group was interested, so he left The Bonzos to help Stephens form a touring version of The New Vaudeville Band, which included original session drummer Henri Harrison. The lead singer of the touring version of the group was Alan Klein, who was billed as 'Tristram - Seventh Earl of Cricklewood'.