Между тем, перейдя под крыло рекордингового лейбла Up Studios и параллельно наладив сотрудничество с Sub Pop, к началу 1996 года команда была готова открыть счет своим будущим хитам. Под эгидой этих двух компаний вышел новый мини-альбома «Interstate 8», включавший ранние демо-записи группы, сингл «Broke», объединенный с песней «Whenever I Breathe Out, You Breathe In» (Positive/Negative)", и, наконец, полноформатный дебют с длинным названием «This Is a Long Drive for Someone with Nothing to Think About» и 16 совершенно новыми песнями. Материала было так много, что пришлось разделить его на два диска. Продюсерские обязанности легли на плечи Стива Вэлда (Steve Wold), который участвовал и в процессе записи. Разрабатывая характерные темы одиночества и отчаяния, молодая команда обогатила звуковую палитру за счет мандолины, слайд-гитары и виолончели, придав саунду особую эмоциональность, резкость и глубину, что сразу выделяло Modest Mouse на фоне их коллег по альт-рок-цеху.

Но настоящий прорыв, в том числе и к более широкой аудитории, совершил второй студийный альбом «Lonesome Crowded West», выпущенный в 1997 году. Это не только одна из лучших работ в каталоге Modest Mouse, но и одна из ключевых записей во всем альтернативном роке конца 90-х. Команда представила драйвовую, динамичную и очень разноплановую запись, порадовав мастерством «на все руки». Modest Mouse так свободно переходили от негромкой обволакивающей акустики к мрачному зубодробительному року или энергичному emo, что не могли не восхитить критиков и не найти преданных почитателей среди поклонников альтернативы.

О тематике песен Modest Mouse можно говорить отдельно и очень долго. Свойственное Айзеку Броку чувство юмора позволяло ему свободно разрабатывать самые странные сюжеты. Скажем, в репертуаре Modest Mouse есть ряд песен на библейскую тематику (на втором альбоме это «Teeth Like God’s Shoeshine» и «Jesus Christ Was an Only Child»), однако они носят, как правило, антирелигиозный характер. Брок не делает секрета из своего убежденного атеизма. «Я уверен, что все христианство — это просто куча дерьма», — заявляет главарь «Скромных мышек» и добавляет, то если он и обращается к Библии, то только потому, что ему нравятся библейские персонажи.

Следующего пополнения дискографии пришлось ждать три года. В самом начале 2000-го вышла компиляция «Building Nothing Out of Something», объединившая би-сайды, записанные в разное время, и три из пяти треков, изданных на мини-альбоме «Interstate 8». А летом 2000 года фаны смогли познакомиться с новинками от Modest Mouse. Третий лонг-плей «The Moon & Antarctica» вышел уже на новом лейбле Epic Records. Стараниями новых покровителей команде удалось прорваться к мейнстриму. Два трека, «3rd Planet» и «Gravity Rides Everything», получили неплохую ротацию на альтернативном радио, а сам альбом отметился в рейтинге Billboard 200, хотя и на непрезентабельной 120-й позиции.

Но тот факт, что массовый слушатель еще не открыл для себя Modest Mouse говорил не в пользу слушателя. «The Moon & Antarctica» был (и остается) очень неплохим альбомом, который отличает сильный, мускулистый саунд и разноплановый материал. В целом минорный по настроению, он эффектно сочетал тяжелые, мрачные номера c оживленными и энергичными композициями. Один из таких живчиков — «Gravity Rides Everything» — приглянулся компании Nissan и прозвучал в рекламе нового мини-фургона. Брок называл этот шаг откровенно коммерческим, но вынужденным — он помог команде достичь финансовой стабильности.