Именно в Тифлисе взошла ее артистическая звезда. Местный театр трещал от поклонников. Темпераментные южные мужчины были опьянены ее божественной красотой и голосом. Андрей Алексеевич с неудовольствием наблюдал за ростом популярности своей супруги. За пять лет она сыграла целый ряд разнообразных ролей — от водевильных простушек до Ларисы в «Бесприданнице» Островского. Пресса отмечала не только сценический дар Марии Федоровны, но и большую музыкальность, особенно после выступления в заглавной роли в оперной постановке «Миньона» Тома. Уроки пения она брала у певицы И. М. Зарудной и имела широчайший диапазон — от нижнего соль до верхнего ля. Вскоре весь Тифлис был у ног Андреевой. В ее честь один за другим следовали обеды и банкеты. Однажды некий влюбленный грузин после витиеватого тоста осушил бокал, а затем съел его, чтобы «никто не посмел пить из моего бокала» после таких слов. Муж в этот момент случайно перехватил чувственный, призывный взгляд Машеньки, адресованный вовсе не ему. Андрей Алексеевич понял, что из Грузии пора уезжать от греха подальше, и выхлопотал перевод в Москву. Он полагал, что его импульсивную, взбалмошную по натуре жену смогут удержать рамки московского высшего общества. Как же он заблуждался!
Москва сразу наполнилась слухами о прелестной и талантливой актрисе. И следует отметить, что на сцене Мария Федоровна и впрямь была царицей. Свое театральное мастерство она шлифовала постоянно, окончила Московскую консерваторию. Ее учителем и партнером на сцене Общества искусства и литературы стал Константин Сергеевич Станиславский. Также она брала частные уроки у знаменитой актрисы Н. М. Медведевой — учительницы непревзойденной М. Н. Ермоловой. Спектакли с участием Андреевой собирали аншлаги. За три сезона Мария Федоровна сыграла одиннадцать ролей. Она дебютировала в пьесе Островского «Светит, да не греет», а затем была Юдифь («Уриэль Акоста»). Актрису хвалили за искренность, чувство меры, поэтичность и пленительную женственность. Она купалась в лучах славы, создав шекспировские образы Геро («Много шума из ничего») и Оливии («Двенадцатая ночь»). Но ярче всего ее дарование раскрылось в роли Раутенделейн в «Потонувшем колоколе» Гауптмана. Зал застывал в восхищении, покоряясь воздушному, романтическому, полному диковатой грации образу, созданному Андреевой. Ее голос, «звучащий серебристым звоном лесного ручья», зачаровывал, оставляя неизгладимое впечатление у публики.
Казалось, что еще нужно женщине — любовь зрителей, восторженная пресса, богатый респектабельный дом, муж, получающий чины, награды и удовлетворяющий любой каприз. Высокопоставленный светский круг общения. Слава. Признание. Богатство. Сама великая княгиня Елизавета Федоровна писала портрет Андреевой. Но всего этого оказалось мало не знающей угомону душе. Семейное счастье оказалось недолговечным. Муж встретил и полюбил другую женщину, да и сама Андреева не осталась равнодушной к репетитору сына Дмитрию Ивановичу Лукьянову. Позже она скромно написала в мемуарах: «Еще в 1896 году я перестала быть женою Андрея Алексеевича Желябужского. Причины нашего разрыва были на его стороне. Я сказала ему, что соглашаюсь жить с ним в одном доме как мать своих детей и хозяйка — ради детей».
Внешне все оставалось благопристойно и вполне респектабельно: роскошная квартира, дорогие наряды и блеск драгоценностей, которые так любила Мария Федоровна. Счастливая жизнь светской женщины. Никто из друзей не подозревал, что она увлечена другим мужчиной и серьезно разделяет его революционные интересы. Андреева, со свойственной ей страстностью, включилась в подпольную работу ставропольского студенческого землячества. Свободные от сцены вечера проводила в спорах на политические и философские темы. Переводила с немецкого и тщательно изучала «Капитал» К. Маркса. Партия большевиков очень нуждалась в таком «товарище» с огромными светскими связями, и вскоре Андреева стала выполнять поручения Московского социал-демократического центра по хранению и транспортировке нелегальной литературы, принимала участие в работе Красного Креста. Пользуясь своими многочисленными знакомствами, она взяла на себя «легализацию подпольщиков, снабжение их документами и трудоустройство».
Даже бурный роман с богатым предпринимателем Саввой Морозовым был изначально запланирован В. И. Лениным и Л. Б. Красиным, чтобы выкачать из него побольше денег на революцию. Андреева и сама была заинтересована в этой интрижке — в творческом плане. Под покровительством влюбленного мецената она могла прочно занять ведущее место на театральных подмостках Москвы. Не оставляя ни подпольной, ни сценической деятельности, Мария Федоровна окунулась в создание Московского художественно-общедоступного театра, где она должна была быть единственной примой. Морозов выделил на строительство 500 тыс. рублей и стал совместно с В. И. Немировичем-Данченко содиректором и крупнейшим пайщиком МХТ. Ради прекрасных глаз возлюбленной Саввушка влезал не только в финансовые дела театра, но и в репертуар, требуя для своей обожаемой Машеньки главных ролей. Станиславский, понимая «полезность» Андреевой, соглашался с требованиями щедрого мецената, а Немирович-Данченко отстаивал негласную царицу Художественного театра и свою ученицу О. Книппер-Чехову.
Конечно, Марию Федоровну это очень обижало, ведь она по праву была соучредительницей театра, участвовала в подготовке Устава, привлекала меценатов, договаривалась с подрядчиками. Станиславский спокойно переложил на ее плечи ведение рутинных дел и целиком отдался творчеству. Андреева несколько лет мужественно выполняла эти обязанности, лишь бы играть ведущие роли в профессиональном театре. За шесть сезонов она с боем отстояла для себя 15 главных ролей в пьесах Чехова, Островского, Гауптмана, Ибсена, Шекспира. Пресса превозносила ее до небес. Театральный критик С. Глаголь после возобновленной постановки «Потонувшего колокола» писал: «Г-жа Андреева, чудесная златокудрая фея, то злая, как пойманный в клетку зверек, то поэтичная и воздушная, как сказочная грёза». А С. Васильев в газете «Новости» добавлял, что в роли Оливии «она была так изящна и красива, настолько соответствовала шекспировскому образу, что напрашивалась на полотно художника».
Этапной ролью в творчестве Андреевой стал образ Кете в пьесе Гауптмана «Одинокие» (1899 г.) — в нем с особой силой проявилось ее лирическое дарование. В этой роли она выходила на сцену 73 раза. Известная актриса В. Л. Юрьева вспоминала свое впечатление от игры Марии Федоровны: «Я до сих пор помню лицо Кете после самоубийства Иоганнеса: Кете падает на пол с зажженной свечой, и пламя играет в ее расширенных, застывших от ужаса глазах. Вообще М. Ф. Андреева в этой роли была так трогательно беспомощна, нежна и прекрасна, что обычное сравнение страдающей женщины со сломанным цветком на этот раз вполне выражало то, что видела публика».
