Recibe esta denominación en noviembre de 1994, en honor al recuerdo de este insigne Oficial de la época Artiguista y la Cruzada Libertadora, conocido como "Señor del Este", conquistando, entre otros hechos relevantes, la Fortaleza de Santa Teresa en 1811, 1825 y 1828.
El General Leonardo Olivera ingresó al Ejército a los 17 años, al iniciarse la Revolución de 1811.
Participó de innumerables batallas, generalmente en el este del país (lo que le dió su apodo), pero también en otros lugares, por ejemplo en el sitio de la ciudad de Colonia, comisionado por el Gral. Juan Antonio Lavalleja.
La Ruta Nacional Nº 9, que une Montevideo con el Chuy (Departamento de Rocha) y pasa al costado del predio del Batallón, lleva su nombre.

La Unidad tiene su origen en el Escuadrón de Caballería Nº 1 creado el 26 de febrero de 1907 y que luego fue transformado en Regimiento de Caballería Nº 11 en la reorganización del Ejército efectuada a partir del 16 de febrero de 1911.

El 24 de febrero de 1919 el personal del Regimiento de Caballería Nº 11 sirvió de base para formar el Batallón de Infantería Nº 19, creado por segunda vez, en la ciudad de Santa Isabel del Departamento de Tacuarembó (actual Paso de los Toros).

El 19 de abril de 1939, el hasta entonces Batallón de Infantería Nº 19 pasa a denominarse Batallón de Infantería Nº 12. Tenía su guarnición entonces en el Departamento de Maldonado, luego de sucesivos cambios de sede en sus primeros 20 años de vida, hasta que el 7 de diciembre de 1939 ocupa su sede actual en la ciudad de Rocha.

El 6 de marzo de 1958 constituyó un destacamento de Represión de Contrabando en el Cuartelillo de San Miguel, que desde entonces ha evolucionado hasta llegar a la actual Compañía que el Batallón mantiene en la zona fronteriza con la República Federativa de Brasil, en el Fuerte de San Miguel.

El 24 de febrero de 2019 el Batallón cumplió 100 años. Entre las actividades de festejo del centenario, se entregó una placa conmemorativa por parte del Batallón Simbólico de Infantería.