Dyplomacja to istotny aspekt gry, który uległ znaczącym zmianom w stosunku do Rome czy pierwszej części Medievala. Dodano nowe rzeczy (np. system priorytetów), poprawiono stare (głównie sztuczna inteligencja). Możliwości naszych dyplomatów są bardzo podobne do tych z Rome. Istotną zmianą jest jednak pokazywanie pięciu współczynników określających daną frakcję: Priorytety (czyli to, czego frakcja może od nas chcieć), Reputacja (wiarygodność), Potęga, Bogactwo, Religia. Po lewej stronie znajdziemy jeszcze Stosunki, czyli relacje pomiędzy państwami. Na górze widnieje Zachowanie, które określa, jak dyplomata reprezentujący drugi kraj będzie odnosił się do naszych propozycji. Współczynniki te są niezwykle pomocne w tworzeniu nowych przymierzy, gdyż mamy dokładniejsze informacje o tym, czy dane państwo będzie skłonne zawrzeć z nami jakiekolwiek stosunki i możemy ewentualnie podjąć konkretne działania, aby poprawić sytuację panującą dwoma nacjami.
Jak wiemy, w Rome dyplomacja była jedynie na papierze, ponieważ agresywna polityka komputera powodowała, iż wszelkie sojusze i pakty okazywały się nietrwałe. Nagminne były sytuacje, kiedy państwo, które utraciło niemal wszystkie prowincje, nie chciało przyjąć protektoratu, mimo iż byliśmy w stanie wyeliminować je paroma kliknięciami myszki. W Medieval II przyjęto inny system. Każde państwo ma, tak jak w Rome, określone cele do wykonania, ale także posiada swoje priorytety, którymi się kieruje. Możliwe stały się dzięki temu trwałe sojusze. Alians możemy umocnić, wydając naszą księżniczkę za dziedzica frakcji sojusznika. Należy jednak pamiętać, iż Medieval to gra historyczna i nie możemy się spodziewać trwałego sojuszu pomiędzy np. Anglią a Francją czy Turkami i Bizancjum.
Niemożliwe będzie też zawarcie przymierza wraz z zajęciem kluczowej dla danej nacji prowincji. Np. jeżeli grając Cesarstwem zajmiemy Hamburg, możemy się spodziewać rychłego konfliktu zbrojnego z Danią. Dlatego czasem warto powstrzymać ekspansję na tereny, które znajdują się w orbicie zainteresowania innej frakcji, gdyż spór o jedną prowincję może spowodować uciążliwą wojnę.
Gdy wygrywamy batalię z jakimś krajem, a nie chcemy go doszczętnie niszczyć, możemy zastanowić się nad opcją „zostań wasalem”. Jeżeli się zgodzi, oba państwa będą miały między sobą sojusz i prawa handlowe, jednak lennik będzie musiał płacić wysoki trybut. Ponadto nie każda nacja godzi się na ograniczenie suwerenności i bardzo prawdopodobne jest, iż odmówi i zdecyduje się na walkę do końca.
Czasem, gdy drugie państwo nie będzie chciało przyjąć naszej propozycji, możemy spróbować zaoferować trochę więcej. Aby przekonać komputer, nic nie stoi na przeszkodzie, by ofiarować mu jakiś region lub trochę pieniędzy. Można także spróbować zastraszyć go atakiem, ale z reguły nie odnosi to oczekiwanego skutku.
Możliwe jest także kupienie lub sprzedanie jakiegoś lenna lub regionu. Oferujemy odpowiednią sumę i wyznaczamy terytorium, którym będziemy handlować. Czasem dobrze jest sprzedawać prowincję, w której trudno utrzymać porządek, nie jest dochodowa i znajduje się na obrzeżach naszego państwa.
Możemy także próbować starej metody, znanej z Rome – sprzedawać mapy. Czasem możemy osiągnąć korzystną cenę, zwłaszcza od bogatego państwa. Handel mapami w Rome był bardzo zyskowny, w Medievalu jest nieco mniej skuteczny, aczkolwiek nadal możemy zarobić trochę cennych florenów, sprzedając informacje topograficzne.
Opłaca się składać oferty wiązane, np. my oferujemy prawa handlowe, sojusz i mapę, oczekujemy tego samego + 2000 florenów, ewentualnie regularny trybut. O ile nasi wysłannicy zdążyli odkryć relatywnie spore połacie Europy, komputer powinien przyjąć ofertę, zwłaszcza we wczesnym etapie kampanii.
Najbardziej dochodowy jednak w grze jest handel. Dzięki niemu możemy zarabiać grube tysiące florenów. Nacje z dobrym położeniem utrzymują się wyłącznie z handlu, podczas gdy kraje muzułmańskie czy wschodnioeuropejskie polegają raczej na rolnictwie i łupieniu miast przeciwnika. Bardzo opłacalne jest zawieranie umów handlowych z innymi państwami i powinniśmy to nieustannie robić, ponieważ pomnaża to znacząco nasze dochody. Dobrze rozwinięte miasto z otwartymi szlakami handlowymi wprowadza do kasy kilka tysięcy florenów na turę. Niestety, za dużo nie pohandlujemy nacjami muzułmańskimi, gdyż nieustannie na nasze prowincje odbywają się krucjaty, przez co większość nacji katolickich wypowie nam wojnę.
Należy jednak pamiętać, iż ta gra koncentruje się na wojnie i nie warto polegać tylko i wyłącznie na dyplomacji – konflikty zbrojne są nieuniknione więc warto ostrzyć miecze i poszerzać swoje imperium.