Até 1969, a região de Erechim possuía guarnições da Brigada Militar pertencentes ao 3º Regimento de Polícia Montada de Passo Fundo, Unidade responsável, na época, pela manutenção da ordem pública em quase toda a região norte do estado.

Em 1970, por ato do então Governador do Estado, Coronel de Polícia Militar Walter Peracchi de Barcellos (Decreto 20.277, de 13 de Maio de 1970) é criada, em Erechim, a 1ª Cia de Polícia Militar Independente (1ª Cia Ind), que toma para si a responsabilidade sobre a região do Alto Uruguai. A instalação efetiva da 1ª Cia Ind se deu em 1º de Julho de 1970.

Em 1974 (Decreto 23.245, de 13 de Agosto de 1974) a 1ª Cia Ind é transformada no 13º Batalhão de Polícia Militar (13º BPM), sendo considerada esta, a data comemorativa do aniversário do 13º BPM.

Em 1988, em homenagem a seu primeiro Comandante, o então Major Cecílio dos Santos, o 13º BPM recebeu a denominação histórica de "Batalhão Tenente Coronel Cecílio".

Hoje, o 13º BPM é composto por dezoito municípios, são eles: Erechim - Sede do 13º BPM, Aratiba, Itatiba do Sul, Tês Arroios, Severiano de Almeida, Mariano Moro, Barra do Rio Azul, Nonoai, Rio dos Indios, Gramado dos Loureiros, Trindade do Sul, Entre Rios do Sul, São Valentin, Faxinalzinho, Benjamin Constant do Sul, Erval Grande, Barão de Cotegipe e Ponte Preta.  

O 13°BPM tem dois grandes programas desenvolvidos pelo batalhão que são o Programa Sentinela e o Programa Novo Rumo.