В 1957 году Быстрицкая продолжала разрываться между театром и кино — играла в Вильнюсском театре и снималась в третьей серии «Тихого Дона». Ее мечтой было перебраться в Москву, в Мекку театральной и кинематографической жизни страны, однако все ее попытки осуществить это долгое время ни к чему не приводили. Например, осенью 1955 года в Доме кино ей посчастливилось познакомиться с Фаиной Георгиевной Раневской, и та порекомендовала режиссеру Театра имени Пушкина, в котором сама играла, взять молодую звезду в труппу. В Пушкинском тогда собирались ставить «Белый лотос», и Быстрицкой была обещана одна из ролей. Однако этим планам так и не суждено было осуществиться.
И все же в столицу Быстрицкая перебралась. Помог ей в этом кинорежиссер Юрий Егоров и его фильм о комсомольцах «Добровольцы», съемки которого проходили в 1957 году. У Быстрицкой там была главная роль — Леля Кайтанова.
Фильм вышел на широкий экран 20 октября 1958 года и принес его создателям огромный успех. Он собрал в прокате 26, 6 млн. зрителей (17-е место), что считалось неплохим результатом. После этого успеха Быстрицкая была замечена и получила приглашение перейти в труппу Малого театра — сначала по договору, а затем (в марте 1959 года) с зачислением в штат. Первой ролью Быстрицкой на сцене Малого стала леди Уиндермиер в спектакле по О. Уайльду «Веер леди Уиндермиер».
Несмотря на то что Быстрицкая была уже достаточно известной и популярной киноактрисой, карт-бланшем для легкого вхождения в коллектив прославленного театра это не стало. Наоборот, это обстоятельство даже в какой-то мере усложнило ей жизнь, потому что корифеи театра относились к кино с некоторым пренебрежением, как к чему-то несерьезному. Кроме этого, Быстрицкой пришлось доказывать свое право играть в труппе театра в жесткой конкуренции с другой киноактрисой, принятой в штат одновременно с ней, — Руфиной Нифонтовой, которая прославилась в 1957 году, сыграв роль Кати в кинотрилогии «Хождение по мукам». Конкурентная борьба буквально изматывала обоих. По словам самой Быстрицкой, первое время работы в Малом она никак не могла войти в стиль этого театра и почти после каждой репетиции мчалась в медчасть принимать успокоительные таблетки.
И все же шаг за шагом ей в конце концов удалось доказать, что ее зачисление в штат Малого оказалось не случайным. В итоге за два последующих сезона (1960–1961) она сыграла сразу шесть ролей: Наталью в «Осенних зорях» В. Блинова, Нину в «Карточном домике» О. Стукалова, Кэт в «Острове Афродиты» А. Парниса, Клеопатру Гавриловну в «Почему улыбались звезды» А. Корнейчука, Катерину Ремиз в «Крыльях» того же автора и Параньку в «Весеннем громе» Д. Зорина. Однако затем в течение полутора лет она сидела без новых ролей. Почему? Причину этого следует искать в излишне прямолинейном характере актрисы.
В Малом тогда ставили спектакль «Мадам Бовари» и режиссером был Игорь Ильинский. Он взял на роль Эммы свою жену — актрису этого же театра Татьяну Еремееву. Когда Быстрицкая узнала об этом, она бросила в сторону Ильинского такую реплику: «Как вы можете дать роль Эммы Бовари Еремеевой, с ее фигурой?» Позднее Быстрицкая признается: «Наверное, следовало его пощадить, но ведь я искренне верила: чтобы играть, нужно как минимум быть в форме. Не то что я была глупа — я была, наверное, неосмотрительна, а возможно, и беспощадна в силу молодости…»
Эта фраза до глубины души оскорбила Ильинского. И он превратился (вместе со своей женой) в ярого врага молодой актрисы. В результате карьера Быстрицкой заметно осложнилась. В 1962 году, накануне премьеры спектакля «Маскарад», где она играла одну из главных ролей (баронессу Штраль), Ильинский выступил со статьей в одном из популярных изданий, в которой говорилось, что в театр приходят кинозвезды, которые ничего не умеют, — имея в виду и Быстрицкую, и Нифонтову (с Козой у Быка тоже не самые дружеские отношения). Далее на одном из партийных собраний он заявил, что Быстрицкая не актриса, а пошлая манекенщица. Однако словесной эквилибристики признанному мэтру, видимо, было мало, и он по мере возможности препятствовал карьере Быстрицкой на деле. Например, когда на телевидении собрались снимать спектакль «Касатка» с Быстрицкой в главной роли (по ее же словам — самая замечательная ее работа), Ильинский сделал все от него зависящее, чтобы эта съемка не состоялась. Кроме этого, Быстрицкой стали давать играть только на сцене филиала театра, практически лишив ее возможности выступать на главной сцене.
Заметим, что Ильинский был не последним человеком, с кем Быстрицкая испортила свои отношения в начале 60-х. Нечто подобное произошло у нее и с Михаилом Шолоховым. Дело было так.