Навчився грати рано, пізніше займався в Харківському Палаці піонерів, де викладав О. Г. Мацкевич. У чемпіонаті країни серед юнаків до 18 років (1966 р.), він розділив 1—2 місця.
Через кілька місяців стався успіх в змаганнях серед дорослих. У півфіналі чемпіонату країни Штейнберг перевиконав норму майстра (стати майстром в 14 років до цього ще нікому не вдавалося)[2]. Після цього йому дозволили виступити (наприкінці 1966 року)[3] за СРСР на чемпіонаті Європи серед юніорів в Гронінгені (Нідерланди), де в фіналі він посів перше місце (6 з 7), обігнавши найближчого переслідувача Ендрю Вайтлі[en] на два очки[4].
Декілько добрих результатів домігся і у 1967 році.
У відбірковому турнірі до юнацького чемпіонату світу розділив 2—3 місця. Став срібним призером чемпіонату ДСТ «Спартак».
У 35-му чемпіонаті СРСР[en] розділив 8—17 місця (15 місце за додатковими показниками) серед 126 учасників. Екс-чемпіон світу Ботвинник назвав М. Штейнберга однією з головних надій радянських шахів.
У міжнародному матчі між Радянським Союзом та Югославією 1968 року Штейнберг зіграв на першій юніорській дошці перед майбутнім чемпіоном світу Анатолієм Карповим.