A origem deste grupamento remonta à década de 40, quando da criação do Esquadrão de Caça Submarino, que depois da Segunda Guerra Mundial foi transformado em Força-Patrulha Costeira do Nordeste (FORPACONE) e, posteriormente, no Grupamento Naval do Nordeste (GNNe), por meio do Aviso Reservado do Ministro da Marinha nº 2106 de 08/09/1967, que adotou a nova Organização Administrativa para as Forças Navais. Na ocasião, o Grupamento Naval do nordeste era composto pelos seguintes navios: Corveta "IPIRANGA", Corveta "FORTE DE COIMBRA", Corveta "PURUS", Corveta "CABOCLO" e Navio-Patrulha "PIRAJÚ".

Em 10/07/1981, o GNNE deixou de ser subordinado ao Comando da Base Naval Ary Parreiras (atual Base Naval de Natal), e passou a constituir um Comando de Força independente, sob a denominação de Comando do Grupamento Naval do Nordeste (ComGrupNNE), com a nomeação para Comandante de um Capitão-de-Mar-e-Guerra do Corpo da Armada. A partir de 26/01/1996 o Comando passou a ser exercido por um Capitão-de-Fragata. Em cumprimento a Portaria nº 192/MB/2006, o Comando do Grupamento Naval do Nordeste (ComGrupNNE) teve sua denominação alterada para Comando do Grupamento de Patrulha Naval do Nordeste (ComGptPatNavNE).