Born in Melbourne to a German-born father, also Max, and an Adelaide-born mother, Kathleen, Teichmann grew up in the working-class suburb of Carlton during the Great Depression.

After leaving school, he worked as a junior journalist, then in 1942 joined the Australian army and saw action in Papua New Guinea.

He won a scholarship to Balliol College, Oxford, United Kingdom where he was taught by Isaiah Berlin, Max Beloff and John Plamenatz.

While in the United Kingdom, Teichmann became involved in left-wing politics, joining Britain's Labour Party and Campaign for Nuclear Disarmament.

He became active in the anti-Vietnam War movement in Australia and counted among his friends leading Australian Labor Party identities such as Jim Cairns and Bill Hayden.