Heinz was born in Detmold, (Germany), but from the age of seven was brought up in Eastleigh, Hampshire, England. His German father had been killed during World War II and his mother decided to move to Britain. Heinz was influenced by the US singer Eddie Cochran and played in a local Eastleigh group, the Falcons, in the 1950s. Working in a Southampton grocery shop Heinz came to the attention of record producer Joe Meek, becoming his protégé. Meek styled Heinz's image, which included persuading him to peroxide his hair.