Localizado na histórica Fortaleza de São José, na Ilha das Cobras, herdou um passado de mais de 147 anos, desde 24 de novembro de 1852, quando teve seu regulamento aprovado pelo Decreto n° 1.067-A, assinado pelo Imperador D.Pedro II. Portanto, o nome Batalhão Naval é uma homenagem às glórias do Btl Naval do século XIX.
Participou da campanha contra Aguirre (República Oriental do Uruguai), destacando-se na batalha da tomada do Forte Sebastopol na cidade de Paissandu (1864).
Durante toda história, o Batalhão Naval participou de diversas operações militares e cívico-militares tendo presença ativa na história brasileira.
Olavo Bilac, lendo pela primeira vez a Oração à Bandeira no pátio do Batalhão Naval em 19 de novembro de 1915. Óleo sobre tela de Álvaro Martins.
Nos dias de hoje, com a especialização do Corpo de Fuzileiros Navais, as atividades operativas foram deslocadas para Organizações Militares específicas, ficando o Batalhão Naval responsável pela manutenção da Fortaleza de São José e pelas representações do CFN.