Quando começaram a ter uma base de fãs , os Muses passaram a tocar em Londres e em Manchester . A banda reuniu-se com o produtor musical Dennis Smith , o dono da Sawmills Studio .

A reunião acabou com o acerto do primeiro EP da banda na casa-gravadora Dangerous . O segundo EP , intitulado de Muscle Museum EP , alcançou a terceira posição na indie singles chart e atraiu as atenções de uma rádio britânica de Steve Lamacq assim como a da conceituada revista inglesa NME , onde ganharam uma publicação . Dennis Smith apresentou a banda para Safta Jaffery , o fundador das empresas SJP/Dodgy Productions , que tinha acabado de fundar uma gravadora chamada Taste Media . Os Muse decidiram assinar um contrato com  Smith e Jaffery que produziram os seus primeiros três álbuns :

- Showbiz

- Origin of Symmetry

- Absoution

Apesar do sucessso do seu segundo EP , as gravadoras britânicas tinham uma certa relutância em assinar contrato com os Muse . Então a banda viajou para Nova Iorque , para o CMJ Festival e uma gravadora decidiu levá-los para Los Angeles para uma apresentação . A banda começou a fazer uma série de apresentações pelo Estados Unidos durante aquele ano (1998) . Foi durante essas viagens que que os Muse assinaram com a Maverick Records . Logo após a banda ter voltado da América , a Taste Media fez com que os Muse assinassem vários acordos com diversas gravadoras pela Europa e atá na Austrália , permitindo que eles fizessem sucesso em diversos países .

O produtor musical John Leckie foi chamado para produzir o primeiro álbum de estúdio da banda , intitulado de Showbiz , em 1999 . O álbum mostrou uma faceta mais leve da banda e as letras retratavam a dificuldade deles enquanto tentavam encontrarem-se no tempo de Teignmouth . Logo após o lançamento do álbum , a banda fez uma turné pelos Estados Unidos e fizeram-se acompanhar pelas bandas Red Hot Chili Peppers e pelos Foo Fighters . Durante os anos de 1999 e 2000 , os Muse tocaram em todos os grandes festivais pela Europa e Austrália .