Самая первая песня певицы стала шлягером, большинство музыкальных деятелей заинтересовались Машей. В 1989 году Распутина исполнила свою песню в финальной части «Песня года», а также завоевала гран-при на фестивалях «В роке только девушки» и «Пхеньян». Одновременно с наградами, молодая певица начинает работать с Леонидом Дербеневым, что укрепило ее звездный статус. Уже в 1991 году певица выпустила первый дебютный альбом «Городская сумасшедшая». Многие были удивлены вокалом Маши и ее раскрепощенностью на сцене. Большинство ее песен рассказывали об ее прошлой жизни, о том, что есть сейчас, и даже о проблемах коррупции, и продажности медицины.
[[Файл:raspu3.jpg|350px|thumb|right|Маша Распутина с Филлипом Филиппом Киркоровым]]
Особый успех артистке принесли композиции «Кружит музыка» и «Гималаи». Дебютный альбом был продан огромным тиражом. После выпуска альбома певица разъезжала по городам России с сольными концертами, собирая полные залы зрителей. В 1992 году Распутина выпустила второй альбом «Я родилась в России», сотрудничая с Игорем Матетой, Александром Лукьяновым и Леонидом Дербеневым.