A primeira tentativa de implantação do serviço dos Correios no Brasil começou em 1520. Na ocasião, em Portugal, era criado o Ofício de Correio Mor do Reino, que era cedido a uma particular para sua exploração, por concessão real. O primeiro a ter privilégio foi Luís Homem.

O Ofício foi vendido à família Gomes da Mata, em 1606. Em 1657, o Ofício do Correio Mor das Cartas do Mar era vendido a Luís Gomes da Mata e anexado ao primeiro ofício. Com isso, o Correio Mor passou a ter seus assistentes naas colônias portuguesas, com objetivo de administrar a expedição e a entrega das correspondências.

Em 1662, os primeiros assistentes foram nomeados em Pernambuco, Bahia e Rio de Janeiro. Assim, essa foi a primeira tentativa de implantação do Correio no País. A tentativa não foi muito feliz devido à pouca aceitação popular em relação ao serviço. A razão desta má aceitação foi a taxação que os assistentes impunham aos objetos postais, antes vindos gratuitamente pelos navios portugueses ou, da mesma forma, quando eram conduzidos ao interior por viajantes solícitos.

A taxação de portes excessivos e a dilatação entre as datas de envio e de entrega acabaram por inviabilizar, na prática, o Correio Mor, que acabou não sendo bem explorado. Assim, as cartas circulavam gratuitamente nos idos dos séculos XVI ao XVIII.

A necessidade de agilizar e incrementar as transações comerciais e de prestar um serviço de comunicação à distância culminou, em 1796 com reincorporação do Ofício à Coroa. O então Príncipe Regente D. João encarregou D. Rodrigo de Souza Coutinho de fazê-lo - era o ministro de Estado da Marinha Domínios Ultramarinos, culminando com o decreto de 18 de janeiro daquele ano e o alvará de 16 de março de 1797.