O primeiro corpo de agentes policiais foi criado por D. Fernando I, os chamados Quadrilheiros, com um efectivo de 20 elementos, tendo recebido um Regimento, datado de 12 de Setembro 1383, que refere no seu preâmbulo a grande criminalidade que grassava na cidade de Lisboa.
Estes Quadrilheiros (recrutados à força, entre os homens mais fortes fisicamente) ficavam subordinados à Edilidade, por três anos consecutivos, e obrigados por juramento a terem as suas armas (uma Vara, que devia estar sempre à porta de cada um deles, a qual representava o sinal de Autoridade para prenderem e conduzirem o criminoso perante a Justiça dos Corregedores).
Cada quadrilheiro era responsável pela chefia de uma quadrilha (patrulha) de 20 homens. Todos os membros da quadrilha andavam armados com uma lança de 8 palmos (1,76 m). Os quadrilheiros tinham, como insígnia, uma vara verde com as Armas Reais.