Born in Vienna to a working class family—his father worked for the tramway—Klestil went to school in Landstraße where he made friends with Joe Zawinul.
Nado en Viena no seo dunha familia de clase obreira -o seu pai traballou para o tranvía- Klestil foi á escola en Landstraße onde fixo amizade con Joe Zawinul.