Tendo sua origem nas instalações do Comando e Serviços da FFE, foi sua área ocupada em 20 de novembro de 1963 pelo Batalhão de Transportes Motorizado do Núcleo da 1ª Divisão de Fuzileiros Navais. Em fevereiro de 1965 foi ativado e instalado o Comando de Serviços da Força de Fuzileiros da Esquadra, tendo como comandante o Capitão-de-Mar-e-Guerra (FN) GUY RENÊ ROBICHEZ SANCHES.

    Em 27 de dezembro de 1971 foi criado o Batalhão de Manutenção e Abastecimento, pelo Decreto nº69.287 de 24 de setembro de 1971 com a mesmo dotação do ex-Comando de Serviços da FFE.
    Dentro do contexto da reestruturação da Força de Fuzileiros da Esquadra (FFE) foi alterada, por portaria Ministerial nº0055 de 18 de janeiro de 1995, a denominação de Batalhão de Manutenção e Abastecimento para Batalhão Logístico de Fuzileiros Navais. Para tal, a Unidade foi acrescida da Companhia de Transportes do Extinto Batalhão de Serviços e da Companhia de Saúde da Base Almirante Leônidas Telles Ribeiro (BALTR). Com isso, visou-se dotar a nova OM de um estrutura operativa que lhe desse condições de executar as tarefas logísticas de manutenção, transporte, abastecimento e saúde.
    Em 23 de fevereiro de 1995, data que se tornou um marco histórico do CFN, foi realizadas, presididas pelo Exmº Sr. Contra-Almirante (FN) MOACYR MONTEIRO BAPTISTA, Comandante da Tropa de Reforço - as cerimônias de passagem de comando do Capitão-de-Fragata (FN) CESAR ESPERANÇA MATOSO para o Capitão-de-Fragata (FN) PAULO ROBERTO BORGES DE SANTANA e a oficialização da nova denominação. O Capitão-de-Fragata (FN) PAULO SANTANA, passou a ter o privilégio de ser o primeiro Comandante do BtlLogFuzNav - O caçula das OM do Corpo de Fuzileiros Navais.