Het verhaal van Mercenaries speelt zich in de nabije toekomst af in Noord Korea, normaal gesproken een niet al te zeer tot de verbeelding sprekend land. Voor een game en de gamer is het echter de perfecte ambiance om dit land te gaan proberen te redden van een kernramp. Chaos alom in het land, de ene militaire coup volgt de andere op. In het land is een behoorlijk aantal partijen aanwezig die stuk voor stuk proberen de orde te handhaven, danwel zelf beter proberen te worden van de situatie aldaar. Het is vervolgens aan jou om als huurling orde in de chaos te gaan scheppen en en passant nog even wat dollars te cashen. We doen het tenslotte niet voor niets. Ziedaar...'Mercenaries' is een feit.
Centraal in de game staat 'The Deck of 52', een lijst van 52 meest gezochte dwarsliggers, waar stuk voor stuk korte metten mee gemaakt moet worden. Dat er in die lijst een zekere hierarchie heerst mag duidelijk zijn. De azen zijn belangrijker om te vangen, de lage cijfers wat minder. Bovenaan het lijstje staat ene generaal Song. Deze generaal heeft de leiding over de 'deck of 52'. In tegenstelling tot wat je zou verwachten is het de bedoeling dat je je tegenstanders levend gaat inrekenen. Maar niet getreurd, mocht je de 'fout' maken een van hen toch een loodvergiftiging te bezorgen, dan kost je dit slechts de helft van je geldelijke beloning die je voor die missie zou moeten ontvangen.
