Так в январе 1999-го начались первые гастроли Muse – музыканты выступили в таких крохотных а-ля туалет, но легендарных залах, как «Роудхаус» (Манчестер), «Крипт» (Гастингс), тесный «Дачесс оф Йорк» в Лидсе и «Танбридж-Уэллс-Форум». На концерт в последнем заведении, знаменитом тем, что когда-то оно на самом деле было публичным туалетом, пригласили Ника Мура из Work Hard, который бесплатно работал на Muse публицистом со времен In The City, и сообщили, что группой интересуется другая пиар-фирма. Вскоре после этого Muse перешли под крыло уважаемой компании Bad Moon PR, которой управлял Антон Брукс, работавший с прессой для Nirvana и The Happy Mondays. Буквально через несколько месяцев они снова сменили пиарщика – на этот раз их выбор пал на новую, еще ничем себя не проявившую фирму Impressive PR, во главе которой стояла бывшая сотрудница Arista Мел Браун – ей очень понравился концерт группы на CMJ. Еще они выступили в «Эсквайрс» в Бедфорде и старом добром «Каверне» в Эксетере, выступая на разогреве у любой группы, которая соглашалась их взять, а потом турне прервалось на полпути – они отправились в Гамбург, чтобы 19 января дать концерт для Universal/Motor в «Лого-Клубе». Пораженные Гуземан и Реннер заключили контракты с Muse в тот же день, жалея, что смогли заполучить права лишь на небольшой территории. Сафта и Деннис пока что остановились на четырех контрактах, радуясь, что на группу работают четыре целеустремленные команды вместо одной; контракты для Японии и Скандинавии они обговорят лишь осенью 1999 года.

Британское турне в поддержку второго релиза, Muscle Museum EP на Dangerous, стало вехой в истории Muse. То была их первая гастроль в качестве группы, подписанной на лейбл, и у них вдруг обнаружился большой белый арендованный фургон, тур-менеджер, букинг-агент и печать одобрения самой Мадонны. Больше того, у них даже появилась собственная команда гастрольных техников, хотя то была довольно разношерстная группа из друзей по Тинмуту и всяких прихлебателей, в том числе удолбанного цыгана, которого они нашли спящим под открытым небом. Тот сказал, что три недели питается одними кукурузными хлопьями и водой, и группа из жалости взяла его мониторным техником. Концерты в Америке помогли Muse понять, что они не такая уж и плохая группа, но резкий переход от выступлений «для своих» перед однокашниками по колледжу и растущей аудиторией в Девоне к показательным выступлениям для шишек из музыкального бизнеса и концертам на разогреве у более известных групп, чьи фанаты ими не интересовались, сделал их интровертами, которые играли для себя, а не для аудитории. Все это было волнующе, пугающе реально и происходило с головокружительной быстротой. Они понимали: чтобы сполна воспользоваться раскрывающимися перед ними возможностями, нужно как можно скорее собраться с силами.

Репетиции стали интенсивными, а концерты – напряженными; сет-лист состоял в среднем из десяти песен: Overdue, Cave, Uno, Instant Messenger, Sober, Fillip, Rain, Muscle Museum, Unintended, Showbiz. Тур из одиннадцати выступлений завершился в «Юнионе», студенческом клубе Лондонского университета, где они отыграли на разогреве у мрачных шведских рокеров Kent; Muse за один месяц дала больше концертов, чем за весь предыдущий год, и быстро превратилась в слаженный, великолепный рок-коллектив. Голос Мэтта превратился в яростный фальцетный визг, от которого могли лопаться стекла, а гитарная игра больше напоминала извержение вулкана и была достойна человека с вдвое бóльшим количеством пальцев. Крис и Дом превратились в громоподобную ритм-секцию, по сравнению с которыми их современники вроде Coldplay выглядели как неуклюжие увальни (которыми тогда, собственно, и были).