Не попав в летное училище, Ульянов в том же 1944 году записался в театральный кружок под руководством Евгения Павловича Просветова. Два года он «грыз» там гранит театральной науки, после чего решил – пора покорять Москву. Купил билет на поезд и отправился в столицу. В ГИТИС экзамены провалил, но зато был принят в то самое щукинское училище, в котором все еще училась Алла Парфаньяк (она была на последнем курсе). Но для первогодка Ульянова она тогда была недосягаема. А когда он узнал, что она к тому же стала женой Николая Крючкова, его мысли о знакомстве с ней и вовсе стали несбыточными. И он переключил свое внимание на других студенток.
В конце учебы у Ульянова завязался страстный роман со студенткой, которая училась на курс младше его – с Ниной Нехлопоченко (1928). Они практически не расставались друг с другом ни в училище, ни за его пределами. Мечтали о том, как вскоре окончат «Щуку», поженятся и будут играть в одном театре до старости. Но, как оказалось, это были всего лишь мечты. Во всяком случае, для Нины. Потому что однажды она уехала навестить своих родных в Одессу, а там, как назло, гастролировал Театр Вахтангова. Нина с подругами отправилась на один из спектаклей и познакомилась с музыкантом театрального оркестра Борисом Веселым (он играл на фаготе). И закрутился у них роман, который заставил девушку иначе взглянуть на свои отношения с Ульяновым. Она поняла, что больше его не любит. О чем она тут же ему и сообщила, вернувшись в Москву.
Сказать, что Ульянов был этим потрясен, значит ничего не сказать. Он был буквально этим раздавлен. Но удерживать бывшую возлюбленную силой он не собирался и во время их последнего свидания сказал: «Дай бог, чтобы тебя кто-нибудь полюбил так же, как я, и чтобы ты не переживала того, что я сейчас переживаю!» Именно в тот миг в нем зародилось дикое желание доказать Нине, что она совершила страшную ошибку, за которую будет корить себя всю жизнь. Он решил во что бы то ни стало стать знаменитым. А уж если он что-то решил, то остановить его на этом пути было очень трудно.
В 1950 году Ульянов окончил училище и был распределен в Театр имени Вахтангова. В тот самый, где работала и Алла Парфаньяк. Но она считалась примой этого театра, одной из немногих его актрис, которая приезжала и уезжала из него на собственной машине, купленной ее звездным супругом Николаем Крючковым. Когда она подъезжала к театру на этом авто и выходила из салона в каракульчовой черной шубке и шляпке, пошитой самой известной в Москве модисткой, прохожие замирали в немом восторге. Разве могла Алла обратить внимание на какого-то безусого дебютантика Ульянова, бегавшего в массовке и одевавшегося, как провинциальный мужлан. Естественно, нет. Михаил тогда был гол как сокол и нищ, почти как попрошайка на паперти. Он жил в общежитии, где вместе с ним в одной комнате обитали еще трое таких же, как и он, нищих студентов. Когда однажды они варили пшенную кашу в кастрюле и та опрокинулась на пол, они вчетвером ползали по нему и ложками ели эту кашу, пока она была еще горячей. Если бы это увидела Парфаньяк, она бы просто упала в обморок от такого зрелища. Но Ульянов в глубине души продолжал верить в то, что его клятва, данная им себе во время последнего разговора с Нехлопоченко, будет выполнена. И шел к этому методично и упорно.
В 1951 году он вступил в ряды КПСС, чтобы эта мечта стала еще ближе. А вскоре после этого он узнал, что у Парфаньяк не все ладится в семье – их брак с Крючковым был на грани распада. Единственное, что удручало – Алла завела себе другого мужчину, причем он был из того же круга избранных, что и Крючков. Это был знаменитый актер Марк Бернес. Он тогда тоже был женат, но в актерской среде это мало что значило – понятия муж или жена там часто носят чисто условное значение. Эту истину Ульянов открыл, еще когда учился в щукинском, и она его тогда здорово поразила. Ведь в тех местах, где он родился и прожил первые 19 лет, такой свободы нравов все-таки не наблюдалось.