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.
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.
Em maio de 1988, a Portaria Ministerial nº 0398/1988 alterou a situação administrativa da PEM, sendo a mesma classificada como com autonomia administrativa.
A PEM ocupou, inicialmente, instalações no Edifício Barão de Ladário. Em cumprimento a diretrizes do então Ministro da Marinha, mudou-se, em 15 de outubro de 1998, para o prédio nº 114 da Rua 1º de Março, anteriormente ocupado pelo Serviço de Assistência Social da Marinha (SASM). Em suas novas instalações, que passaram por obras no sistema de captação de águas pluviais e na instalação elétrica, ocupa, no térreo, a portaria e o corredor de acesso à escada que conduz aos demais pavimentos, e a totalidade do 1º e 2º pavimentos, o último dos quais possui um mezanino (Auditório e Praça d'Armas).
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 1997, os Advogados de Ofício transferiram-se para Defensoria Pública da União, no Rio de Janeiro. Os Procuradores foram transpostos para a carreira de Assistentes Jurídicos da União da Advocacia Geral da União (AGU) a partir de 2000 e transformados em Advogados da União, da carreira correspondente da AGU, em junho de 2002, permanecendo, porém, em exercício na PEM, com as mesmas atribuições.
Doravante, os Procuradores a serem admitidos, o serão através de concurso público para Advogado da União, promovido pela AGU, e após, efetuarão um curso específico no CIAGA, onde serão introduzidos na arte naval, na navegação e outros assuntos marítimos, a fim de que possam bem desempenhar suas funções nesta Procuradoria Especial da Marinha.