Klejn was born in Vitebsk, Belarus, to two Jewish physicians, Polish-born Stanislav Semenovich Kleyn (originally Samuil Simkhovich) and Asya Moiseyevna nee Rafalson (Russian: Рафальсон).

In 1941, both of Klejn's parents were drafted to serve in World War II, while the rest of the family were evacuated, first to Volokolamsk and then Yegoryevsk near Moscow, and then to Yoshkar-Ola in the Mari ASSR.

Graduating with honours from the Faculty of History in 1951, Klejn worked as a librarian and high school teacher for six years before returning to Leningrad for postgraduate studies in archaeology.

He was awarded a Candidate of Sciences degree (equivalent to a PhD) in 1968, defending a thesis on the origins of the Donets Catacomb culture.

[clarification needed] Then in the seventies he began working on theoretical problems in history and archaeology—a subject that had been completely neglected since Stalin's purges of academia in the 1930s—and found himself contradicting the orthodox Marxist theory of historical materialism.

In the early 1970s Klejn's brother Boris, then teaching in a Grodno institute, was dismissed and stripped of his degree and title for speaking against the introduction of Soviet troops into Czechoslovakia.

Klejn neither affirmed nor denied the charge, even after homosexuality was decriminalised, on the basis that an individual's sexual orientation is not the concern of society or the state.

Eventually the initial sentence was overturned by a higher court and commuted to eighteen months detention, which by this time Klejn had almost served.

He recorded his prison experiences under the pen name Lev Samoylov in the journal Neva[2][3][4][5] and in his own name in the book The World Turned Upside Down.

Afterward, he was a visiting scholar at a number of institutions, including the Universities of West Berlin, Vienna, Durham, Copenhagen, Lubljana, Turku, Tromse, Washington in Seattle and the Higher Anthropological School of Moldova.

Klejn's elaboration of a special theory for archaeology went against the Soviet view that historical materialism was the only theoretical basis of the humanities.

Klejn places particular emphasis upon rigorous methods of interpretation, in order to guard against the manipulation of antiquities in the service of political aims.

This 'systemic' approach, which has been influential in Russian archaeology,[10][11][12] stressed that some initial knowledge about the material to be classified as a whole is necessary to construct a reliable system of classification, and therefore that the process must work 'backwards' (relative to the received procedure) from cultures to attributes.