Учась на 4-м курсе, Клейн написал критическую работу о Марре и отдал ее на просмотр своему научному руководителю М.И. Артамонову, который нашел выводы студента настолько интересными, что предложил обсудить его работу на специальном заседании Ученого совета в Институте истории материальной культуры Академии наук СССР. Такое беспрецедентное обсуждение и состоялось 3 марта 1950 года, причем оппонентами студента выступили такие светила археологии как Б.Б. Пиотровский, А.П. Окладников, А.Н. Бернштам и декан исторического факультета ЛГУ В.В. Мавродин,
Но несмотря на блестящую учебу, красный диплом, высокую оценку его научных достижений М.И. Артамоновым, путь в аспирантуру в обстановке начавшегося в 1951 году разгула антисемитизма Клейну был закрыт. Надо заметить, что выдающиеся способности Клейна были признаны самыми пристрастными судьями – сокурсниками, которые дали ему прозвище «великий». И конечно дело было не только в игре слов (klein по-немецки значит маленький, и Клейн высоким ростом действительно похвастаться не мог), а в том, что он вел себя не как робкий студент, а как имеющий свою независимую точку зрения состоявшийся ученый, умеющий убедительно ее отстаивать.
Почти шесть лет Клейн посвятил работе школьным учителем, сначала в Ленинграде, а затем в Гродно. Однако годы преподавания в школе не были вычеркнутыми из его жизни. Клейн, верный своему принципу (и завидному умению) даже жизненные поражения обращать себе на пользу, совершенствовал свое педагогическое и преподавательское мастерство – серьезно изучал методику преподавания, проверял ее на практике, тренировался в том, чтобы говорить о сложных вещах просто, доходчиво, занимательно, живо, афористично, владеть аудиторией. Уж если кто с детьми и трудными подростками сладил, то студенческую аудиторию «держать» сможет наверняка. Впоследствии это весьма пригодилось. Многие доктора наук ныне признают, что некоторые лекции Клейна помнят до сих пор и могут повторить их слово в слово.
После доклада Хрущева на XX съезде КПСС начался новый период в жизни страны. Клейн почувствовал оттепель с некоторым запозданием. Весной 1957 года в Гродно пришло письмо, в котором сообщалось, что М.И. Артамонов предлагает ему поступать в аспирантуру при кафедре археологии. Начался период активной научной и преподавательской деятельности Клейна на кафедре археологии ЛГУ, сначала в качестве аспиранта, затем после полутора лет пребывания в статусе безработного, в качестве ассистента, а после защиты кандидатской диссертации – доцента.
Казалось бы, при выдающемся таланте и высокой работоспособности написать и защитить кандидатскую диссертацию для Клейна не составит труда и займет, всего несколько лет. Однако между моментом поступления в аспирантуру и защитой прошло 11 лет. Причина состоит в том, что Клейну было неинтересно пойти по пути развития своего диплома в кандидатскую диссертацию, как это делает большинство аспирантов. Поэтому он взялся за разработку темы, которая больше подошла бы для докторской диссертации, – «Происхождение скифов-царских», а потом сменил ее на новую тему – «Происхождение Донецкой катакомбной культуры». Одновременно он писал книгу «Спор о варягах». В срок диссертация не была защищена: и не столько потому что, по признанию Клейна, «проблема оказалась достаточно трудоемкой (я взял на себя слишком много)», а потому, что по своему характеру он не мог ограничиться разработкой одной идеи. Ему были свойственны, по его собственному выражению, метания – в результате возникали новые оригинальные идеи, требовавшие немедленной разработки.
С 1962 года начинается двадцатилетнее преподавание Клейна на кафедре археологии Ленинградского университета. Он вел там разные курсы – как обязательные: основы археологии (введение в археологию), методика полевых исследований, методика кабинетных (историко-археологических) исследований, методика камеральной обработки, археология бронзового века, история археологических знаний, так и факультативные: археологическая разработка норманнского вопроса, археология катакомбной культуры, археология культур боевого топора и шнуровой керамики, археологическая типология, теоретическая археология и другие.
В 1980 году после ввода советских войск в Афганистан и срыва политики разрядки напряженности начался самый трудный и драматический период в жизни Клейна – он был арестован. Тогда официально считалось, что в Советском Союзе нет политических заключенных. Поэтому всем арестованным по политическим мотивам предъявлялись чисто уголовные обвинения. Клейн был обвинен в гомосексуальных связях.