Но удача все-таки не обошла их стороной. В 1998 году в одном из баров, где выступала группа, они познакомились с продюсером местного лейбла Taste Media и после недолгих переговоров перебрались в Лондон. Музыкантами заинтересовалась пара крупных американских лейблов, которые пригласили Muse в Нью-Йорк на CMJ. После триумфального концерта интерес к группе в США возрос и спустя две недели они уже выступали в Лос-Анджелесе на Santa Monica Pier. Под рождество было принято предложение лейбла Мадонны Maverick и заключены контракты на выход альбомов Muse в Германии (Motor Records), во Франции (Naive) и в Великобритании (Mushroom Records) — через пять лет напряженного поиска группа заполучила сразу четыре успешных контракта. Дебютный одноименный EP и выпущенный затем сингл “Muscle Museum”, вышедший небольшим тиражом, разошелся за несколько недель.

Спустя некоторое время к группе присоединился Джон Леки, работавший с Radiohead над альбомом “The Bends”. Через месяц вышел сингл “Uno”, который несмотря на все обвинения Muse в подражании Radiohead занял 75-е место в британском хит-параде. После нескольких удачных выступлений на различных фестивалях группа вернулась в США и провела большое турне. Осенью 1999 года в свет вышел дебютный альбом “Showbiz”, который получил большую популярность не только в Великобритании, но и в США. Диск стал золотым и разошелся по всему миру тиражом более 500.000 экземпляров.

В феврале 2000 года Muse получили премию NME Premier Awards в номинации «Открытие года» и затем отправились в большое мировое турне в поддержку дебютной пластинки. Группа выступала с такими известными командами, как Red Hot Chili Peppers, Foo Fighters, Skunk Anansie и Pavement.

В сентябре 2001 года коллектив посетил Россию, где выступил на презентации русской версии журнала New Musical Express в «Лужниках». Незадолго до этого группа выпустила свой второй альбом “Origin Of Symmetry”. В следующем году Muse порадовали своих фэнов двойным концертным альбомом “Hullabaloo” и во второй раз приехали в Россию.

Следующий альбом группы под названием “Absolution” увидел свет в 2003 году. Группа по-прежнему экспериментировала с классическими влияниями, и некоторые критики отметили, что на новом альбоме хард-рок Muse обрел практически вагнеровский размах. Основная тема альбома была выбрана под стать - конец света и возможные реакции на него. С новым альбомом Muse удалось заключить выгодный контракт в Штатах, и вскоре они отправились в международное турне. Гастроли имели успех, и летом 2003 года группа выступила в качестве хедлайнера престижного английского фестиваля в Гластонберри, разделив это звание с Oasis и Полом Маккартни. «Это был самый важный концерт в нашей жизни», - делился позже своими впечатлениями Мэттью Беллами. Турне продолжалось до начала 2005 года – впрочем, в пути были небольшие остановки. Так, во время одного из концертов Беллами умудрился разбить губы о собственную гитару, и ему пришлось делать операцию. Несколько концертов были отложены, однако Мэттью довольно быстро пришел в норму и сумел продолжить концерты. Турне закончилось двойным выступлением в Earl’s Court Arena в Лондоне – группе пришлось назначить дополнительный концерт, поскольку спрос на билеты был просто ошеломительный. Группе также досталась награда журнала Q в номинации «Лучшая концертная группа».

2 июля 2005 года Muse приняли участие в масштабной благотворительной акции “Live 8”, а осенью 2005 года приступили к работе над новым альбомом. С сентября по октябрь группа писалась во Франции, а потом перебралась в Нью-Йорк. В интервью телеканалу MTV Беллами заявил, что хотел бы сделать новый альбом «более положительным, обнадеживающим». Альбом “Black Holes & Revelations” вышел в июле 2006 года.