Но мечта о сцене не давала покоя. Она снова и снова обивала пороги театров и наконец в 1869 году, стараниями отца, дебютировала в Минске, в пьесе «Бедовая бабушка». Так началась её театральная жизнь.
Тут нужно заметить, что хотя отец и старался всеми силами помочь дочери утвердиться на сцене, сделать что-то серьёзное был совершенно не способен, поскольку сам так и не достиг каких-то сценических успехов. То есть учить мастерству он был не способен.
Но в Минске на Машеньку обратила внимание актриса и писательница Ирина Семёновна Сандунова (1811–1891), супруга театрального деятеля и писателя Фёдора Алексеевича Кони. Урождённая Юрьева, она оставила для сцены фамилию первого мужа — Сандунова. Публиковалась же она под девичьей фамилией. К примеру, в 1837 году при поддержке писателя А. Ф. Вельтмана, приходившегося ей родственником, издала первый сборник рассказов «Повести девицы Юрьевой». Ну а в «Литературной газете», журнале «Репертуар и Пантеон» помещала статьи под девичьей фамилией — Юрьева. Актриса великолепно исполняла комические женские роли свахи в «Женитьбе» и городничихи в «Ревизоре» Николая Васильевича Гоголя. В «Грозе» Островского с блеском исполнила роль Кабановой. В театре пользовалась авторитетом и имела определённое влияние на руководство. Ну и занялась обучением юной начинающей актрисы, определив в ней несомненный талант.
Забегая вперёд, необходимо отметить, что именно в Минске Мария подружилась с сыном своей учительницы Анатолием Фёдоровичем Кони (1844–1927), который был на десять лет старше, но сразу полюбил актрису, сохранив в тайне своё чувство, пронесённое им через всю жизнь.
Что же касается юной Машеньки, то она испытывала к Анатолию Кони лишь чисто дружеские чувства, а вот сердце своё в ту пору она готова была отдать Владимиру Ивановичу Костровскому, влюблённому в неё и опекавшему её в театре. Костровский был отставным поручиком, красавцем, покорившим немало женских сердец в Смоленске, Минске и Твери. Биограф Савиной И. И. Шнейдерман отметил, что «В. И. Костровский оберегал Савину от закулисных интриг, добивался для нее подходящих ролей и „подавал“ в спектаклях так умело, что ее быстро оценила публика».
Однако не всё гладко было в его деятельности антрепренера, говаривали, что был любителем пьянок-гулянок и опускался до мошенничества.
Тем не менее благодаря ему Мария Гавриловна настолько утвердилась на сцене, что минский губернатор отдал распоряжение театральному руководству повысить ей денежное содержание.
В 1869 году состоялся бенефис. Савина блестяще сыграла роль Полиньки в пьесе к тому времени уже известного русского драматурга Александра Николаевича Островского (1823–1886) «Доходное место».
Выступала она тогда ещё под родительским сценическим псевдонимом — Стремлянова.
Очевидно, Владимир Костровский имел виды на Машеньку. Трудно сказать, собирался ли он жениться или планировал лишь стать любовником, но помощь оказывал большую. Пользуясь связями, добивался для юной актрисы интересных ролей в ведущих спектаклях и выгодных контрактов.
Но тут случилось непредвиденное. Проведав, что дочь твёрдо обосновалась в Минске, к ней явилась мать и, узнав о Костровском, устроила скандал, пуще тех, что бывали в Одессе. Поскандалила она и в театре, чем лишила возможности продолжать там работу. В результате Мария Гавриловна оказалась в Харькове. Там снова работа, напряжённая работа над собой. Она не играла — она жила на сцене, словно компенсируя там то, что недополучила в реальной жизни. Зрители скоро заметили её.

Мария Савина
Но долго ещё была на подхвате. Она тянулась к знаниям, но учёба закончилась давно, и остался один источник — книги.
Разъезжала с отцом, выступала, если удавалось. И вдруг в одной из «бродячих групп» в самый ответственный момент не смогла выступать актриса. Её попробовали заменить Марией. Получилось. И тогда юную актрису взяли в труппу, и в 15 лет она получила свой первый ангажемент. Понятие «ангажемент» происходит от французского engagement — обязательство, наём. Наём или приглашение артиста на заранее оговариваемый срок для участия в спектаклях или концертах.
Вот так, ни дня не учившись театральному искусству, она оказалась на сцене уже не в качестве случайной, используемой для срочной замены, а как бы профессиональной актрисы. У отца учиться было нечему — он сам не имел серьёзных ролей. С матерью пришлось разлучиться, да и та вряд ли бы могла чему-то научить.
Правда, мать уговорила взять её в харьковскую антрепризу Дюкова.
Именно в Харькове юная актриса вышла замуж. А случилось так, что среди театральных интриг, подсиживаний, сплетен, зависти появился человек, который поддержал её в конфликте.
В Харькове у Марии Стремляновой на первых порах не было никого, кто бы мог помочь в продвижении по театральным ступеням. В Харькове было особенно трудно. Театр был хорош. Каменный, построенный антрепренером Людвигом Млотковским, 1842 году. И в этом театре Мария Стремлянова оказалась одна. Она испытала одиночество, беспомощность и унижение. В театре поначалу публика Марию не восприняла. То ли потому, что маленькая — шестнадцать лет, или просто новенькая.
Однажды Мария услышала разговор за кулисами. Говорили о ней. Она остановилась, прислушалась.
— Что эта новенькая может на сцене? — говорила актриса, которую Мария узнала по голосу — та постоянно придиралась к ней, вредничала.
Вторила ей другая, голос которой был тоже знаком:
— Действительно. Весь спектакль портит!
Подступили обида и боль, а диалог продолжался:
— Пусть это будет её самая последняя роль. Либо я — либо эта выскочка. Ничего, я добьюсь, что её вышибут из театра.
— Да сама уйдёт, если условия создадим.
В это время кто-то подскочил к говорившим.
— Вы что мелете? Как не стыдно!.. Она настоящая актриса, оставьте её в покое.
Мария узнала голос Николая Славича, статного красавца, который всегда был с ней приветлив. Николай Николаевич Славич имел сценический псевдоним Савин.
Когда актрисы удалились, о чём-то возмущённо переговариваясь, Мария подошла к Славичу.
— Вы мой спаситель! Я не знаю, как вас благодарить, — проговорила она.
— Что вы, что вы?! Мне даже неловко такое слышать, — горячо отвечал Славич.
Разговорились. Мария рассказала о своей судьбе, о мытарствах на пути на сцену.
Славич слушал с большим вниманием.
— Как интересно. Вы уже в детстве играли на сцене? Ну я же этим сплетницам сказал, что убеждён в вашем таланте.
А когда Маша поведала о своём первом бенефисе, Славич сделал комплимент:
— Вы восхитительны всегда. И особенно сегодня.
Мария смутилась.
Она знала, что этот актёр нравится женщинам, что он бывший военный. И вот он, Николай Николаевич Славич, обратил на неё внимание, поддержал против разнузданных товарок, а теперь стоял рядом и делал комплименты. Так завязалось знакомство, а вскоре он предложил ей стать его женой. Так на сцене появилась Мария Савина, именно Савина, а не Славич. Савин оказался приятелем Костровского. Много, как выяснилось в дальнейшем, было между ними общего…
Некоторое время работала в харьковской труппе М. В. Лентовского.
Наконец появилась возможность учиться. За ее обучение взялась ученица одного из основоположников русской театральной школы Михаила Семёновича Щепкина (1788–1863) актриса Александра Ивановна Шуберт (1827–1909), более известная как театральный педагог по второму браку Яновская.
Движение по театральной иерархической лестнице не спасало от семейных неурядиц, которым всегда очень способствует безденежье. У артистов невысоких рангов оно зачастую бывало хроническим, даже несмотря на самоотверженную работу. Весь день Савина проводила в театре на репетициях, а ночью учила новые роли, причём сама готовила, перешивала к ним костюмы.
И вдруг — первый успех. Когда она буквально за гроши выступала в Нижнем Новгороде на ярмарке, куда была приглашена для увеселения публики, её заметил актёр, режиссёр и антрепренёр Пётр Михайлович Медведев, происходивший из театральной семьи, показавший себя замечательным театральным деятелем. Он пригласил семнадцатилетнюю Савину в свою труппу. Начались гастроли. Медведев вывозил свою труппу в Казань, Саратов, Орёл и другие города.
Постепенно, шаг за шагом она шла к сценическому мастерству, основой которого всё-таки оставался её природный талант.
Савина получала роли в различных спектаклях — драмах, водевилях, опереттах, комедиях. Так продолжалось до 1872 года, а в 1873 году Марию Гавриловну сделали ведущей актрисой Саратовского театра.
Виктор Антонович Шомпулев (1830–1913), предводитель дворянства Саратовской губернии, председатель губернского земского собрания, губернской земской управы и председатель съезда мировых судей, большой поклонник Савиной, в «Записках старого помещика» рассказал, что у Марии Гавриловны в этот период появился всесильный и богатый покровитель — банкир, миллионер А. П. Коваленко. Правда, в дальнейшем что-то не заладилось в их отношениях, и, «по словам» Шомпулева, Савина «отплатила самой чёрной неблагодарностью». Причём случилось это в период, когда Коваленко оказался на грани полного разорения.