La Armada del Mar Océano creó en 1657 una seríe de compañías en Cadiz para la guerra con Portugal que una vez agrupadas conformaron el Tercio de Infantería de la Armada del
Mar Océano. En su evolución tuvo diferentes reorganizaciones como Tercio Provincial de Madrid (1664),  Tercio de los Colorados Viejos (1694) en guerra con Francia, Regimiento de Infantería Sevilla nº 36 con acuartelamientos en Cataluña, Valencia y Málaga (1707) y cambios de numerales, participó en la guerra de la Independencia (1808-1812) participando en las batallas de Medina de Rioseco, Bilbao, Espinosa de los Monteros, Tamames, Medina del Campo, etc. Participó en las guerras carlistas, guerra de Cuba con un batallón expedicionario (1895-98) y en la recuperación de posiciones en el Protectorado de Marruecos (1921-26). 

En 1931 con el advenimiento de la República le fue fusionado el Regimiento Cartagena nº 70 teniendo su acuartelmiento en Cartagena. Al inicio de la guerra civil en 1936 quedó disuelto. En 1939 al finalizar la guerra civil se reorganizó en Cartagena un regimiento al que se llamaría Regimiento de Infantería nº 34 que en 1943 se renombró Regimiento de Infantería Sevilla nº 40 quedando adscrito a la Base Naval hasta su disolución en 1960.