There had been an office of the Provost Marshal with the ability to arrest and punish soldiers for desertion, plundering or outrage stretching back centuries. These were formed on an ad hoc basis and were disbanded when campaigns and wars were over. Wellington somewhat formalised the system into a staff corps with responsbility of keeping order in the ranks during the Napoleonic War. This force was technically disbanded at the end of the war, although it did continue for a while to police the occupied territories of France until Bourbon rule could be reestablished.
A similar force was raised to serve during the Crimean War. However, this force was to prove more durable. Senior NCOs from several cavalry regiments were invited to form the new service. They had to be of good character with at least five years of unblemished service. When the Crimean War ended, the unit was thought to be useful enough to reconstitute back in Britain and it was billeted at Aldershot.
It is said that the familiar red cap was designed by the wife of a Provost Marshal serving with the unit during the Egyptian campaign in 1882. Another theory was that it was descended from a red scarf tied around the right shoulder used during the Napoleonic Campaigns to identify one another.