A Procuradoria Especial da Marinha, com sede na cidade do Rio de Janeiro, teve sua origem na criação do Tribunal Marítimo pelo Decreto nº. 20.829, de 21 de dezembro de 1931, que previa a atuação de um Procurador especial, como representante do Estado, junto ao Tribunal Marítimo do Distrito Federal, sendo-lhe designado um Procurador da República.
Posteriormente, a Lei nº 2.180, de 05 de fevereiro de 1954, que dispõe sobre o Tribunal Marítimo, previu a existência, junto a esse Tribunal, como órgão auxiliar, de uma Procuradoria, atribuindo-lhe, inclusive, competências. Em 10 de abril de 1960, a Lei nº 3.747 reorganizou essa Procuradoria junto ao Tribunal Marítimo, cujo Regimento Interno foi aprovado pelo Decreto nº 49.748, de 31 de dezembro de 1960 e revogado pelo Decreto nº 96.011, de 06 de maio de 1988.
Pela Lei nº 7.642, de 18 de dezembro de 1987, a Procuradoria junto ao Tribunal Marítimo passou a constituir a Procuradoria Especial da Marinha (PEM), denominação que guarda até os dias atuais . A PEM encontra-se diretamente subordinada ao Comandante da Marinha. A Lei nº 7.642/1987 criou, ainda, o cargo de Diretor da PEM, exercido por um Oficial Superior da Marinha, podendo, quando houver necessidade de serviço, ser o cargo ocupado em comissão, pelo critério de confiança.
Por força da Lei Complementar nº 86, de 12/01/1994, Lei Orgânica da Defensoria Pública da União, as atribuições dos advogados de Ofício foram transferidas para aquela DPU.
Em maio de 1988, a Portaria Ministerial nº 0398/1988 alterou a situação administrativa da PEM, sendo a mesma classificada como OM de autonomia administrativa.
Pela Portaria nº 623, de 19/07/2000, da AGU, publicada no DOU, de 20/07/2000, os Procuradores Especiais então locados na PEM foram transpostos para a carreira de Assistente Jurídico da Advocacia-Geral da União, permanecendo em atividade na PEM, embora formalmente lotados no então Núcleo de Assistência Jurídico da União do Rio de Janeiro (NAJ/RIO). Finalmente, por força do enquadramento no inciso I, art. 11, da Lei nº 10.549/2002, os Procuradores Especiais foram transformados em Advogados da União. No entanto, nenhuma Lei extinguiu ou reformulou as atribuições da PEM previstas na sua Lei Orgânica.
De início, a PEM era constituída por Procuradores e Advogados de Ofício, todos admitidos em concurso público de provas e títulos, específicos para os respectivos cargos. Todos foram submetidos às provas de direito e as de navegação, arte naval e outros afins.
Em decorrência da Portaria Conjunta, Nº 3, de 30 de julho de 2014, publicada no DOU, de 05/08/2014, do Consultor-Geral da União e do Comandante da Marinha, as atividades da PEM nos processos da competência do Tribunal Marítimo, passaram a ser exercidas pelos Oficiais do Quadro Técnico da Marinha, excepcionando-se as atividades de consultoria e assessoramento jurídicos.