太古の昔、南北に分かれた二つの大陸は間に大洋を挟み対照的な発展を遂げた。
北大陸では、フレア王国が高度な工業力と強大な軍事力を背景にして、勢力圏を拡大。
周辺国を衛星国家として併呑しながら、北大陸全域を支配下に置いていった。
一方、南大陸のキリアロス国では豊富な地下資源の所有権を巡って部族間の戦火が絶えずにいた。

北大陸の平定を成し遂げたフレア王国が次に目をつけたのが資源豊かな南大陸のキリアロスだった。
フレア王国は平和維持目的と称し、軍事介入により、瞬く間にキリアロスを平定していった。

キリアロスに傀儡政府を打ち立て豊富な地下資源から得られる富をどん欲に吸収するフレア王国。
そんな王国と傀儡政府へ反発する組織『キリアロス解放軍』が現れる。

続発する解放軍の反政府暴動に対処するため、王国直属の現地雇用兵部隊が創設された。
それが王国外征軍植民地連隊、通称『コロネア』――

金、名誉、名声を求めて集まった様々な傭兵隊が所属する『コロネア』の中でも
『王国の犬』と称される弱小傭兵隊「灰狼傭兵隊」の物語である。