Подобно множеству других датских металлических команд этой группе долгое время пришлось ждать, когда крупные фирмы оторвут свой взгляд от шведско-норвежских тяжеловесов и заметят таланты в их небольшой стране. Проект "Mercenary" был основан в 1991 году жителем Аалборга Гансом Генриком Андерсеном по кличке Краль. Балансируя между трэшем и дэтом, ведомый им коллектив попутно решал кадровые проблемы и за несколько первых лет своего существования произвел на свет пару демо, "Domicile" и "Gummizild". Первая профессиональная запись появилась в 1996 году - это был EP "Supremacy", материализованный с помощью "Black Day Records". К тому моменту партнерами Краля являлись Расмус Якобсен (ударные), Николай Бринкманн (гитара) и Якоб Мольбьерг (гитара).
Та же конфигурация в 1998-м выпустила полноценный альбом "First Breath", включавший в себя как трэшевые, так и дэтовые элементы. После выхода пластинки в студийной работе возникла продолжительная пауза, одной из причин которой вновь стал кадровый вопрос.
Mercenary К 2002 году Бринкманна сменил Сигнар Петерсен, но наиболее повлиял на музыку "Mercenary" приход братьев Сандагеров, вокалиста Миккеля и клавишника Мортена. Миккель противопоставил свой чистый голос гроулингу Андерсена, а присутствие Мортена добавило в саунд мелодичности и атмосферности. После выхода альбома "Everblack" Кралю пришлось уволить Якобсена, поскольку тот уделял группе слишком мало внимания. Образовавшуюся вакансию занял Марк Парк Нильсен, но вскоре по личным причинам в отставку подал и Петерсен, чей инструмент перешел к Мартину Буусу. В 2004 году команда провела национальное турне в компании с "Evergrey", после чего ей удалось пристроиться под крышу крупного лейбла "Century Media".
Альбом "11 Dreams", с которым музыканты дебютировали на этой фирме, представлял собой смесь трэша, дэта и пауэра. Работа заставила обратить внимание на датских металлистов, и многие критики написали одобрительные рецензии.
Mercenary В том же году "Mercenary" выступили на разогреве у "Brainstorm", а в 2005-м помимо участия в "Wacken Open Air" они сопровождали "Nevermore" в их европейском туре. Гастрольная жизнь плохо отразилась на настроении Краля, и лидер команды, посвятивший своему детищу 15 лет жизни, оставил коллег на произвол судьбы. Впрочем, "Mercenary" к тому моменту уже являлись самостоятельной (и довольно известной) единицей, так что следующий альбом записали без своего наставника. Все вокальные партии взял на себя Миккель, на басу сыграл продюсер Якоб Хансен, а получившийся результат "The Hours That Remains" обозначил шаг в сторону прогрессива.
Уже по окончании сессий Андерсену была найдена постоянная замена в лице Рене Педерсена. В мае 2006-го новый бас-гитарист получил боевое крещение на фестивале "Saegfestival", а в августе одновременно с "The Hours..." вышел сборник демотреков "Retrospective". Весной 2008 года группа выпустила студийник "Architect Of Lies", на котором попыталась вернуться к саунду периода "Everblack".
