На протяжении лета HIM дали концерты в Австрии, Голландии, Чехии, Германии, Дании, Финляндии, Швеции, Греции, Португалии и Швейцарии. После выступления на фестивале «Terremoto» в Германии 29 августа ребята взяли отпуск в преддверии начала основной части гастрольного тура в поддержку альбома. "Поэтому мы и издали альбом в апреле. В наши планы входил продолжительный тур с несколькими концертами в каждом городе в небольших клубах", — поясняет Вало.

Впереди группу ждало турне по Великобритании на разогреве у Оззи Осборна и серия концертов в Германии. Первым выступлением после шестинедельных каникул стало появление на "Senssi/Musikki & Media Festival" в Тампере. Однако 9 декабря пришло сообщение, что Оззи Осборн серьезно повредил колено во время занятий спортом, и тур был отменен. Не отчаявшись, ребята организовали свое собственное мини-турне по Британским островам, открывшееся 19 декабря аншлаговым выступлением в уже знакомом им клубе "Astoria".

После новогодних каникул и традиционного выступления в «Tavastia» началась работа над организацией самого грандиозного тура группы, состоявшего из более ста концертов по всему миру. Начав с выступления 19 января в Милане, музыканты проехали через Францию и Люксембург и отыграли пять концертов в Великобритании, билеты на которые были распроданы за неделю до шоу. "Это было наше третье турне по Британии. На первом концерте в двухтысячном году нас слушали человек 30; во второй раз их стало 200–300. А сейчас, наверное, что-то случилось или эти островитяне просто с ума посходили, но мы неожиданно стали здесь безумно популярны!"

Между выступлениями в Испании в феврале HIM записали кавер-версию песни Нейла Даймонда "Solitary Man". В съемках клипа, режиссером которого снова выступил Бэм Марджера, приняла участие звезда телесериала «Зачарованные» Роуз Макгоуэн. Она исполнила роль прекрасной верной любовницы, вокруг которой построен сюжет текста. Песня была одной из двух новинок наряду с треком "And love said no", вошедших в издание "And love said no: The greatest hits 1997–2004". Повторив историю успеха "Wicked Game", песня "Solitary Man" подтвердила, что качественно сделанная кавер-версия может открыть команду для новой слушательской аудитории. Песня не только заняла первое место греческого хит-парада, но и добралась до вершины чартов в Финляндии. Кроме того, трек занял шестую строчку национального хит-парада Соединенного Королевства.

"And love said no: The greatest hits 1997–2004" поступил в продажу 15 марта. Для новообращенных фанатов HIM это был отличный способ увидеть историю творчества группы в ретроспективе. Что до верных поклонников, альбом был снабжен дополнительными шестью треками, записанными во время концерта в клубе «Semifinal» в апреле 2003 года. "Большинство поклонников знало группу только по "Love Metal", поэтому компиляция старого и нового материала позволила всем тем, кто знал только пару наших песен или вообще не слышал о нас, познакомиться с нашим творчеством более подробно, — пояснил Вилле. — На диске собраны практически все синглы, выпущенные нами в Европе за последние 7 лет. Подбирая песни, мы поняли, насколько изменились и мы сами, и наше творчество".Сборник покорил греческий хит-парад, вошел в пятерку лучших в Финляндии и Германии и доказал, что у группы имеется слушательская аудитория даже в Канаде, где диск вошел в первую сотню национального хит-парада.

В середине февраля группа анонсировала грядущий тур по США, состоящий из 22 концертов с апреля по май 2003 года. Группа выступила в нескольких пусть и небольших, но легендарных клубах. В Нью-Йорке это был клуб "Bowery Ballroom", а в Лос-Анджелесе — знаменитый "Whisky A Go Go" на бульваре Сансет.

Вилле считает это турне логичным шагом на пути к глобальной известности. "Последние пять лет я шутил, что репетирую в Европе перед настоящей славой в Америке: Что ж, мы готовы. Мир велик, и я счастлив, что маленькими шажками мы покорили уже большую его часть, — поделился Вало с корреспондентом "Modern Fix" Эрин Бродли. — Хотя, конечно, если мы не станем первой группой, давшей концерт на Луне, или если мне так и не доведется полежать в одной барокамере с Майклом Джексоном и Мадонной, я буду страшно разочарован!"

Турне по Америке обернулось настоящим успехом. Билеты на все концерты были распроданы задолго до намеченных дат, а цена на черном рынке порой доходила до 200 долларов и выше. "Большинство ребят знало наизусть наши песни, даже те, что ещё не были выпущены в Америке, — с гордостью рассказал Виле Вало. — Для меня это стало очень приятным сюрпризом. Я-то боялся, что в США нам придется в своем роде путешествовать во времени и начать все сначала!"

По возвращении из Америки музыканты взяли двухнедельный отпуск, после которого отправились в летний тур по музыкальным фестивалям Европы. После короткого посещения уже прочно завоеванных Греции и Италии HIM вернулись в северную часть Европы с выступлением на фестивале «Donnington» 6 июня, где они были объявлены хедлайнерами второй сцены. Однако, к большому недовольству музыкантов, их время на сцене было ограничено всего шестью песнями. "Мы чуть было не отказались выступать вовсе, — вспоминает солист. — Но потом подумали обо всех тех людях, что приехали на фестиваль только ради нас. В конце концов, это не их вина, что у «Slayer» проблемы с техникой!"

На следующий день HIM выступили на второй ежегодной церемонии вручения музыкальных наград "Metal Hammer", где Вилле получил статуэтку Золотого Бога и звание лучшей рок-звезды года. И этот высокий титул он вполне оправдал, до самого утра вместе с Гасом отрываясь на вечеринке.

После появления на музыкальных фестивалях в Италии, Швеции, Финляндии, Греции и Швейцарии HIM решили отдохнуть пару недель перед напряженным туром по Великобритании, намеченным на октябрь 2004 года. Однако творческая энергия Вилле Вало не знала покоя и отдыха.

В передышках между гастролями он умудрился записать дуэт с солистом «Rasmus» Лаури Юлоненом для песни «Apocalyptica» "Bittersweet" и поработать со старыми товарищами «Skreppers», "69 Eyes" и "Torpedo".

В сентябре группа подписала контракт на четыре альбома с американской звукозаписывающей компанией «Sire». Пакет прав предусматривал и выпуск альбомов за пределами Америки, исключением стала лишь Финляндия, где диски все так же планировалось выпускать на собственном лейбле группы "Heartogram".

Покинув «BMG», музыканты рассчитывали на предложение компании «Sony», но в борьбе за контракт победу одержала звукозаписывающая компания «Sire», сделавшая себе имя в 1970-1980-х и долгое время опекавшая таких мастеров, как Мадонна, «Ramones» и "The Cure". Компания, входящая в концерн «Warner», произвела хорошее впечатление на менеджера группы Сеппо. "Их агенты посетили все выступления группы и сумели привлечь к ним внимание прессы. В Нью-Йорке на пресс-конференции были абсолютно все — от "High Times" до "New York Times". Хотя, прослышав о переходе прав, компания «Universal» выпустила "Deep Shadows And Brilliant Highlights" на рынок 28 сентября без всякой промоподдержки, альбом, даже поданный слушателю в «холодном» виде, вошел в 200 лучших дисков по продажам в Штатах".

Чтобы укрепить свой успех в Америке, группа наметила на конец ноября, сразу после британских гастролей, ещё один тур по США. Через день после аншлага в лондонском "Hammersmith Apollo" ребята уже играли в массачусетском клубе "The Worcester". Так начался двухнедельный клубный тур по Америке. На разогреве у HIM выступали металлисты "Monster Magnet" и сольный проект бывшей басистки «Hole» и "Smashing Pumkins" Мелиссы Ауф дер Мор. "Секрет успеха в том, чтобы постоянно напоминать о себе, — пояснил в интервью одной из финских газет Сеппо. — На весну у ребят запланирована запись нового альбома, а потом они опять едут в Америку. На этот раз турне будет уже гораздо большего масштаба".