Отправной точкой истории группы можно считать 1996 год, когда Мария Макарова передала демо-запись своих песен гастролировавшему в
городе Краснодаре солисту группы "Мегаполис" Олегу Нестерову. В 1997 году М. Макарова подписывает контракт с Олегом Нестеровым,
который и становится ее продюсером.. М. Макарова собирает музыкантов в 1997 году.
Продюсерами нового образования становятся - фирма "Снегири-музыка". В 1997 году М. Макарова переезжает в Москву и приступает к записи своего первого альбома. В этом году группа "Маша и Медведи" снимают два видеоклипа в Индии - "Любочка" и "Б.Т." ("Без тебя"). Режиссером стал Михаил Хлебородов. Все стихи и музыка написаны солисткой группы Машей Макаровой. В 1998 году был подписан контракт на выпуск альбома с фирмой грамзаписи "Extraphone".
Альбом и группа становится "Открытием 1998 года" на Фестивале "Maxidrom", организованным радиостанцией "Maximum" в спорткомплексе "Олимпийский". В 1998 году группа начинает активно гастролировать. Средства массовой информации признают достижения коллектива:
"Матадор" - лучшая группа 1998 года, "ОМ" - лучший дебют 1998 года, "Московский Комсомолец" - певица 1998 года, радио "Maximum" - лучшая песня 1998 года "Любочка", MTV-Russia - "Любочка" - 12 место в итоговом Чарте и 3 место в итоговом Рооссийском хит-параде, журнал "CooL" - 35 недель в хит-параде, альбом "Солнцеклёш" - 28 недель в Top 10 "CooL". Песня "Любочка" из альбома "Солнеклёш" продержалась в хит-параде "Московского Комсомльца" 16 недель, успев 4 раза достичь первого места. После столь удачного старта группа "Маша и Медведи" снимает в 1998 году видеоклип на песню "Рейкьявик" в Исландии. Второй хит успешно принят критиками и группа "Маша и Медведи" принимает участие в широкомасштабных фестивалях: "Сочинская Ривьера" - июнь 1998, "МегаХаус" - июнь 1998, "Праздник города" - сентябрь 1998
года, город Киев.
В 1998 году коллектив отправляется в свой первый гастрольный тур по 15 городам страны. В это время у М. Макаровой появляются идеи о создании второго альбома группы. В 1998 популярный ди-джей Грув делает группе ремикс на песню "Любочка". На это творение снимается видеоклип. В 1999 году готовится материал "Маша и Медведи" принимают участие на фестивале, организованном журналом "FUZZ" в городе Санкт-Петербург. За один год, с апреля 1998 года до апреля 1999 года, группа "Маша и Медведи" даёт 84 концерта в Москве и по регионам СНГ.
В 1999 году во время записи второго альбома Маша Макарова и Олег Нестеров (cолист группы "Мегаполис") записывают песню "Цветы". На эту же композицию снимается видеоклип. MTV-Russia дает самую горячую поддержку этой песне.
В 1999 голу группой "Маша и Медведи" был записан второй альбом под названием "Куда?". Альбом вышел 8 марта 2000 года на "Экстрафоне" (Олег Нестеров и "Снегири" занимаются только промоушном Маши и Медведей). В этом альбоме стихи и музыку также написала М. Макарова. Были сняты два видеоклипа на "Землю" - один мультипликационный и второй - игровой, который снимался в феврале 2000 в Крыму. Для схемок были выбраны так называемые "лес Роу и скалы Роу", которые так часто любил снимать в своих фильмах-сказках знаменитый кинематографист.и организован тур.