Segundo a tradição, o território do Município de São Fidélis era habitado, primitivamente, pelos índios coroados e puris.

A primeira incursão de civilizados deu-se por volta de 1780, contando-se entre os pioneiros Ângelo Severo da Silva, Faustino Cabral, Pedro Dias, Luiz Coelho e um oficial sapateiro, cujo nome não chegou até nossos dias. Sua história está, no entanto, ligada a do Município; esse operário fixou-se nas fraldas de uma serra, que posteriormente tomou o nome de Serra do Sapateiro. Reza ainda a tradição que esse pioneiro e seus dois filhos foram mortos pelos índios coroados, sendo poupada apenas sua filha, levada para as tabas.

Por essa época havia na região somente moradias esparsas de colonos, que viviam sob constante ameaça dos aborígines, notadamente dos índios coroados.

Fato curioso é que tenham sido esses mesmos selvagens que viessem solicitar a vinda da civilização para aquelas plagas. É Monsenhor Pizarro, em suas Memórias Históricas, quem relata: "Os índios coroados que habitavam os sertões de Campos dos Goitacazes, pelas margens do Paraíba, dando demonstrações de quererem aldear-se, vinham freqüentemente, à vila de São Salvador dos Campos (atual cidade de Campos), pedir um sacerdote pare seu diretor, até que o mestre-de-campo João José de Barcelos, prevendo o bom resultado que podia colher-se de um aldeamento, comunicou ao vice-rei Marquês de Lavradio, as favoráveis pretensões que manifestavam os coroados.

O vice-rei não quis deixar de aproveitar-se deste ensejo para fundação de mais um povoado e para conduzir facilmente os indígenas à vida social e faze-los perder toda a repugnância que porventura tivessem pelos costumes civis, tão contrários aos hábitos arraigados de uma vida nômade. Ordenou ao mestre-de-campo que enviasse alguns deles à cidade do Rio de Janeiro. Contentes com o agasalho que lhes deram, satisfeitos com os carinhos e desvelos que lhes foram prodigalizados, voltaram os índios, engrandecendo e exagerando as qualidades e maneiras do vice-rei e foram levar ao conhecimento de seus irmãos a sua admiração pelas habitações que viram, pelas comodidades sociais que presenciaram e gozaram, pela ordem que observaram em tão grande, vasta e populosa aldeia, como pare eles seria a Capital do nosso Império.

Foi assim que, interessando-se pela vida local, o vice-rei tomou as primeiras providências para que ali se erguesse uma grande aldeia para os indígenas. Foram incumbidos dessa missão os frades capuchinhos Frei Vitório de Cambiasca e Frei Ângelo Maria de Luca que chegaram às terras do atual Município de Campos em 14 de setembro de 1781.

Partiram dali os frades capuchinhos à procura de local apropriado para o aldeamento, tendo atingido, no dia 27, um sítio conhecido por Gamboa, onde encontraram boa acolhida por parte dos índios coroados. Exatamente nesse local, ergue-se hoje a cidade de São Fidélis, em região fronteira ao Rio Paraíba.

No dia seguinte à chegada dos frades, foi celebrada a primeira missa em oratório improvisado, depois transformado em capela, dedicada ao culto de São Fidélis de Sigmaringa. E, apenas oito anos passados, a povoação florescia, impondo-se a construção de um templo. A 8 de setembro de 1799, foi lançada a pedra fundamental da igreja, tendo sido inaugurada a 23 de abril de 1808. É essa igreja, a atual Matriz de São Fidélis.

Em 1812 a localidade recebeu o predicamento de curato e em 1838, já ali existindo um Juiz de Paz, participava da Junta de Paz dos Campos de Goitacazes, criada pela Deliberação de 13 de outubro.

Em virtude do grande desenvolvimento da agricultura, ao lado da exploração da madeira de lei,

o povoado progrediu rapidamente, sendo elevado à categoria de freguesia em 1840.

Em 1847, a 12 de abril, recebeu a visita do Imperador D. Pedro II em casa do coronel João Manoel de Souza, mais tarde Barão de Vila-Flor. É do historiador Inácio Raposo o relato que se segue: "Numa visita que dispensara o monarca às obras que se faziam no zimbório da majestosa igreja de São Fidélis, disse o futuro Barão de Vila-Flor ao ilustre soberano que admirava as belezas do Paraíba: que linda povoação é esta para uma vila! O Imperador sorriu discretamente e respondeu-lhe: Será! "