1660s, "action of going the rounds" (of a military camp, etc.), from French patrouille "a night watch" (1530s), from patrouiller "go the rounds to watch or guard," originally "tramp through the mud," probably soldiers' slang, from Old French patouiller "paddle in water," which is probably from pate "paw, foot" (see patten). Compare paddlefoot, World War II U.S. Army slang for "infantry soldier." Meaning "those who go on a patrol" is from 1660s. Sense of "detachment of soldiers sent out to scout the countryside, the enemy, etc." is attested from 1702.
"to go the rounds in a camp or garrison, march about as a guard," 1690s, from patrol (n.) and in part from French patrouiller. Related: Patrolled; patrolling.