Handlinga i spelet er sett til mellom år 1080 og 1530. Likt det opphavlege Medieval fokuserer spelet på mellomaldersk krigføring, religion og politikk i Europa, Nord-Afrika og Midtausten. Men i motsetning til forløparen strekker M2:TW seg inn epoken med oppdaginga av Den nye verda, og simulerer oppdaginga og erobringa av Amerika. Medieval II er bygd på kodar frå Rome: Total War.