Jedním ze závěrů summitu NATO v Praze v roce 2002 byl požadavek Aliance na vytvoření mezinárodní jednotky Vojenské policie (MNMPBAT – Multinational Military Police Batalion), která by poskytovala policejní ochranu ozbrojeným silám Severoatlantické aliance.
Vedoucí role při výstavbě praporu se zhostilo Polsko. Přijalo tak největší část závazku k němuž se z členských zemí Aliance připojilo ještě Slovensko a Česká republika a z programu Partnerství po mír Chorvatsko.
Od roku 2004 probíhala intenzivní jednání k základním dokumentům a legislativnímu rámci. Prvním velmi významným dokumentem pro tvorbu praporu bylo Memorandum o porozumění, které podepsali ministři obrany zúčastněných zemí v období od května do srpna roku 2006.
Od loňského listopadu se schází štáb praporu a řeší standardizované operační postupy pro tuto mezinárodní policejní jednotku.
Prapor či jeho části tak mohou plnit úkoly policejní ochrany úkolového uskupení NATO, nebo samostatně působit při policejních operacích ve světě. Mezi takové operace patří operace na podporu míru, poskytovaní humanitární pomoci při odstraňování následků katastrof a kalamit, operace k zajištění evakuace nebojujícího obyvatelstva a vojenská pomoc a podpora civilních úřadů.
Dohoda rovněž obsahuje ustanovení o podmínkách za jakých může být jednotka použita při operacích s válečnými zajatci. Vybavení praporu umožňuje nasadit je kdekoliv na světě.
Česká republika přispívá do struktury praporu několika příslušníky štábu včetně náčelníka operační skupiny a především četou dopravně pořádkové služby.
Specifickým rysem naší účasti je skutečnost, že na rozdíl od ostatních států nevyčleňujeme do mnohonárodnostního praporu organickou jednotku, ale máme předurčené příslušníky z celého území republiky s ohledem na jejich odborné a jazykové schopnosti a zkušenosti z nasazení v zahraničních misích, kteří v případě aktivace četu vytvoří.
Převážnou část tohoto úkolu nesou příslušníci Velitelství Vojenské policie Olomouc.
Dne 12. června 2007 na slavnostním nástupu podepsali vedoucí představitelé Vojenské policie zúčastněných zemí provádějící dohodu, která mimo jiné stanoví organizační strukturu a koncepci nasazení v různých typech operací NATO.
V září 2012 v polském Wędrzynu došlo k certifikaci Mnohonárodnostního praporu, který je k dispozici Alianci k případnému nasazení.
