Nastanak VP-a OSRH usko je vezan uz početak Domovinskog rata i nastanak samostalne Rebublike Hrvatske. Kako je krenulo ustrojavanje HV-a, krenulo je i ustrojavanje VP-a. U kolovozu 1991. započeto je ustrojavanjem postrojbi VP-a. Takva odluka je donesena na razini državnog vrha, tako da je 24. kolovoza predsjednik Franjo Tuđman tadašnjem načelniku stožera zapovjedništva ZNG-a izdao kratku i jednostavnu zapovijed: ustrojiti vojnu policiju odmah!
Prva postrojba VP-a je ustrojena već 27. kolovoza kada je iz sastava 1. brigade ZNG-a izdvojen 1. bataljun i formiran Zaštitni bataljun ZNG-a. U rujnu i listopadu formiraju se u brigadama HV-a satnije ili vodovi VP-a, a zaštitni bataljun ZNG-a postaje 66. bojnom VP-a. Već u to vrijeme djeluje oko 110 postrojbi VP-a jačine desetine do bataljuna. U vojnopolicijskom smislu organizacija i ustrojavanje VP-a započela je tek ustrojavanjem i djelovanjem Uprave VP-a u studenom 1991. na čelu s Matom Laušićem kadu su se sve postrojbe VP stavile pod vođenje i zapovijedanje Uprave VP-a. Postrojbe VP-a u Domovinskom ratu nisu bile klasične u smislu da su obavljale samo vojnopolicijske zadaće, već su obavljale i ratne zadaće. Nakon rata uslijedilo je konsolidiranje redova i transformacija iz ratne u mirnodopsku vojsku. S 2002. godinom i početkom velikog preustroja, VP-a prelazi s ingerencije MORH-a pod ingerenciju GS-a OSRH-a.[3] Osim u brojčanom smanjenju koje je bilo najintenzivnije 2003. godine, u 2008. godini preustroj je značajne promjene donio i u organizacijskom smislu. Uprava Vojne policije preustrojena je u Odjel Vojne policije GS OSRH-a. Uz to postrojbe Vojne policije ustrojene su unutar grana Oružanih snaga. Tako je u HKoV-u ustrojena pukovnija vojne policije, u HRM-u je satnija vojne policije koja djeluje unutar zapovjedne satnije HRM-a, dok je u HRZ-u ustrojen vod vojne policije. Pukovnija vojne policije u HKoV-u obnaša oko 80 posto ukupnog vojno-policijskog posla u Hrvatskoj.