På trods af de nylige bestræbelser på at udvikle byen, er de ydre byområder stadig truet af udenforstående. Saracens spejder grænserne, mens vikinger plyndrer rigdom og husdyr. Selv byzantinerne fra øst har vist deres mørkere side. Som ædle mænd og kvinder skal spillere samle arbejdere fra byen for at forsvare sig mod fjender, opbygge befæstninger og sprede tro over hele landet. Heldigvis er du ikke alene. I sin store visdom har kongen sendt sine fineste riddere for at hjælpe i vores bestræbelser. Så klar hestene og skærp sværgerne. Paladinerne nærmer sig.
Paladins of the West Kingdom har som mål at være den spiller med flest sejrpoint (VP) i slutningen af spillet. Point opnås ved at bygge outposts og befæstninger, idriftsætte munke og konfrontere udenforstående. Hver runde indhenter spillerne hjælp fra en bestemt Paladin og samler arbejdstagere til at udføre opgaver. Når spillet skrider frem, vil spillerne langsomt øge deres tro, styrke og indflydelse. Disse påvirker ikke kun deres endelige score, men de vil også bestemme betydningen af deres handlinger. Spillet afsluttes i slutningen af den syvende runde.