A história do povoado de São José dos Gatos está vinculada a Francisco Régis Filho, na época comerciante local e proprietário de terras que se destacavam pela grande quantidade de gatos do mato, também chamados de maracajás. O comerciante tinha costume de comprar couro de gato nos domingos de missa e de feira. Por causa dos primeiros moradores da propriedade chamada Gatos serem devotos de São José, Francisco Régis mandou construir uma capela para o padroeiro. Foi então que surgiu da boca do povo a terra de São José dos Gatos.

Só no presente século é que a povoação passou a chamar-se Rodolfo Fernandes em homenagem ao filho da terra, Rodolfo Fernandes de Oliveira Martins, comerciante e industrial renomado, com forte atuação na indústria salineira em Macau e em Mossoró. Foi Presidente da Intendência Municipal de Mossoró, de 1926 a 1928 e organizou a emboscada que repeliu o ataque de Lampião e seu bando à terra de Santa Luzia.

Em dezembro de 1953, em virtude do crescimento econômico e populacional, o povoado de Rodolfo Fernandes, passou a categoria de distrito. Após nove anos como distrito, em 9 de maio de 1962, pela Lei no 2.763, desmembrou-se de Portalegre e tornou-se município.

A cidade possui uma tradição religiosa muito forte, com realizações de novenas, terços e a famosa Festa de São José, padroeiro da cidade. Outro exemplo de devoção está na crença nas Meninas das Covinhas, cuja capela é sede de uma grande celebração todo dia 12 de outubro, data reservada às crianças. A história das meninas - mortas durante a seca do fim do século XIX - é nebulosa e recheada de mistérios, mas uma coisa é certa: os habitantes acreditam, mesmo sem o aval da igreja católica, que as meninas realmente realizam milagres.

À mesa dos Rodolfenses, muita comida sertaneja da boa. O baião de dois, a carne assada, o pirão de peixe, as comidas de milho, o carneiro e a galinha caipira são artigos indispensáveis ao paladar dos habitantes. Em termos econômicos, o artesanato e a castanha de caju são os destaques.

Rodolfo Fernandes tem uma cultura diversificada, sendo um dos atrativos do município. As mãos sincronizadas dos nossos gatos, as lendas do boi e caboclinhos, os pés fortes dos caboclos da malhação de Judas, o romantismo da araruna, a alegria das quadrilhas, a tradição Rodolfense e a cultura de vários povos em um só lugar, assistidos pelos mais diversos públicos com sede de cultura. A Cultura do município é baseada na busca da valorização das tradições e dos costumes mantidos vivos pelos fazedores de cultura local, numa mescla das mais distintas manifestações culturais, através de intercâmbios artístico-cultural entre os inúmeros grupos existentes na cidade.

Formação Administrativa Distrito criado com a denominação de Rodolfo Fernandes ex-povoado de São José dos Gatos, pela lei estadual nº 60, de 21-12-1953, subordinado ao município de Portalegre-RN. Em divisão territorial datada de 1-VII-1955, o distrito de Rodolfo Fernandes, figura no município de Portalegre. Assim permanecendo em divisão territorial datada de 1-VII-1960. Elevado à categoria de município com a denominação de Rodolfo Fernandes, pela lei estadual nº 2763, de 09-05-1962, desmembrado de Portalegre. Sede no atual distrito de Rodolfo Fernandes ex-povoado de São José dos Gatos. Constituído do distrito sede. Instalado em 28-02-1963. Em divisão territorial datada de 1-VII-1960, o município é constituído do distrito sede. Assim permanecendo em divisão territorial datada de 2007.

O município recebeu no ano de 2006 da equipe do projeto Selo UNICEF – Município Aprovado, este ligado ao Fundo das Nações Unidas para Crianças e Adolescente o título de: Rodolfo Fernandes - A Cidade dos Gatos, fato associado a origem da cidade e retratado através de um espetáculo teatral para a equipe do projeto que se encantou com o mesmo, e assim rendeu o título ao município.

Rodolfo Fernandes é um dos poucos municípios do estado do RN a ser contemplado com o Selo UNICEF – Município Aprovado em todas as edições desde que o projeto chegou ao estado no ano de 2006. Sendo premiado nas edições: 2006 – 2008 – 2009-2012 – 2013-2016.

Rodolfo Fernandes realiza a 29 anos o maior e melhor Arraia de Rua do alto oeste potiguar, uma festa que fomenta a economia, o turismo e a cultura local, mantendo viva a tradição do povo nordestino e rodolfense.