И все же в столицу Быстрицкая перебралась. Помог ей в этом кинорежиссер Юрий Егоров и его фильм о комсомольцах «Добровольцы», съемки которого проходили в 1957 году. У Быстрицкой там была главная роль — Леля Кайтанова.

Фильм вышел на широкий экран 20 октября 1958 года и принес его создателям огромный успех. Он собрал в прокате 26, 6 млн. зрителей (17-е место), что считалось неплохим результатом. После этого успеха Быстрицкая была замечена и получила приглашение перейти в труппу Малого театра — сначала по договору, а затем (в марте 1959 года) с зачислением в штат. Первой ролью Быстрицкой на сцене Малого стала леди Уиндермиер в спектакле по О. Уайльду «Веер леди Уиндермиер».

Несмотря на то что Быстрицкая была уже достаточно известной и популярной киноактрисой, карт-бланшем для легкого вхождения в коллектив прославленного театра это не стало. Наоборот, это обстоятельство даже в какой-то мере усложнило ей жизнь, потому что корифеи театра относились к кино с некоторым пренебрежением, как к чему-то несерьезному. Кроме этого, Быстрицкой пришлось доказывать свое право играть в труппе театра в жесткой конкуренции с другой киноактрисой, принятой в штат одновременно с ней, — Руфиной Нифонтовой, которая прославилась в 1957 году, сыграв роль Кати в кинотрилогии «Хождение по мукам». Конкурентная борьба буквально изматывала обоих. По словам самой Быстрицкой, первое время работы в Малом она никак не могла войти в стиль этого театра и почти после каждой репетиции мчалась в медчасть принимать успокоительные таблетки.

И все же шаг за шагом ей в конце концов удалось доказать, что ее зачисление в штат Малого оказалось не случайным. В итоге за два последующих сезона (1960–1961) она сыграла сразу шесть ролей: Наталью в «Осенних зорях» В. Блинова, Нину в «Карточном домике» О. Стукалова, Кэт в «Острове Афродиты» А. Парниса, Клеопатру Гавриловну в «Почему улыбались звезды» А. Корнейчука, Катерину Ремиз в «Крыльях» того же автора и Параньку в «Весеннем громе» Д. Зорина. Однако затем в течение полутора лет она сидела без новых ролей. Почему? Причину этого следует искать в излишне прямолинейном характере актрисы.

В Малом тогда ставили спектакль «Мадам Бовари» и режиссером был Игорь Ильинский. Он взял на роль Эммы свою жену — актрису этого же театра Татьяну Еремееву. Когда Быстрицкая узнала об этом, она бросила в сторону Ильинского такую реплику: «Как вы можете дать роль Эммы Бовари Еремеевой, с ее фигурой?» Позднее Быстрицкая признается: «Наверное, следовало его пощадить, но ведь я искренне верила: чтобы играть, нужно как минимум быть в форме. Не то что я была глупа — я была, наверное, неосмотрительна, а возможно, и беспощадна в силу молодости…»

Эта фраза до глубины души оскорбила Ильинского. И он превратился (вместе со своей женой) в ярого врага молодой актрисы. В результате карьера Быстрицкой заметно осложнилась. В 1962 году, накануне премьеры спектакля «Маскарад», где она играла одну из главных ролей (баронессу Штраль), Ильинский выступил со статьей в одном из популярных изданий, в которой говорилось, что в театр приходят кинозвезды, которые ничего не умеют, — имея в виду и Быстрицкую, и Нифонтову (с Козой у Быка тоже не самые дружеские отношения). Далее на одном из партийных собраний он заявил, что Быстрицкая не актриса, а пошлая манекенщица. Однако словесной эквилибристики признанному мэтру, видимо, было мало, и он по мере возможности препятствовал карьере Быстрицкой на деле. Например, когда на телевидении собрались снимать спектакль «Касатка» с Быстрицкой в главной роли (по ее же словам — самая замечательная ее работа), Ильинский сделал все от него зависящее, чтобы эта съемка не состоялась.