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