Heyme was born in Bad Mergentheim. His parents were ballroom dancers who had run away together as adolescents to run a dance school in Cologne. After his father's death from typhoid in World War II, his mother Erika married Kurt Joachim Fischer who became a prominent journalist and screenplay writer in post-war Germany. After the war, the family settled in Heidelberg where Heyme received his secondary education at the Helmholtz Gymnasium. After graduating from the gymnasium in 1955, he briefly studied architecture in Karlsruhe, but then moved to Heidelberg University where he spent seven semesters studying sociology, German studies and philosophy as well as taking acting lessons.
Heyme was Erwin Piscator's pupil and assistant in Berlin and Mannheim in 1956. He then worked as an assistant director at the Heidelberg Castle Festival and as an organizer of the International Filmfestival Mannheim-Heidelberg. He also appeared in Bernhard Wicki's 1958 cult film
Warum sind sie gegen uns? for which his stepfather had written the screenplay.