Pouco tempo após o nascimento da filha Vitória, em 4 de abril de 1907, em Campina Verde – MG, o imigrante italiano Pelegrino Benelli e sua mulher, Antônia, atravessaram o rio Grande se instalaram nas imediações do ribeirão dos Patos e do córrego das Pontes. Era uma região habitada apenas por fazendeiros e longe dos centros urbanos como Barretos, Olímpia e São José do Rio Preto. Essa solidão do sertão, levou Benelli a pensar num povoado e tomou a iniciativa de doar uma área próximo ao córrego das Pontes.
Acompanhando seu gesto, outros fazendeiros também fizeram doações e formaram uma gleba de 38 alqueires que foi doada para a formação do patrimônio do Senhor Bom Jesus. Isto aconteceu em 28 de setembro de 1911. O povoado foi surgindo aos poucos e logo ganhou o nome de Arraial dos Patos. Era como os engenheiros e agrimensores chamavam a região por causa da grande quantidade de patos existentes próximo aos veios de água, todos afluentes do rio Grande; e, também, por causa do ribeirão dos Patos. Dois anos depois, em 1913, foi criado o Distrito Policial do Arraial dos Patos, dentro do município de Barretos e, quatro anos depois, em 1917, passou a pertencer a Olímpia.
Pela Lei Estadual n 1.801, assinada em 29 de novembro de 1921, o governador Washington Luís, foi criado o Distrito de Paz de Patos, no município e a comarca de Olímpia, com as seguintes divisas: começam na barra do córrego Barreirão, no rio Grande, sabem pelo Barreirão até sua cabeceira mais alta; daí, em rumo ao ponto mais próximo do rio Turvo, descem por este até sua confluência com o rio Grande e, por este acima, até a barra do Barreirão, onde tiveram começo.
O governador Adhemar de Barros assina em 30 de novembro de 1938, o Decreto nº 9.775, fixando o novo quadro de divisão territorial do estado e, entre outros, cria o município de Paulo de Faria, com dois distritos de paz, Orindiúva e Veadinho, com as seguintes divisas:
- Com o estado de Minas Gerais, começam no rio Grande, na foz do rio Turvo, e vem por aqueles até a barra do Porto Velho.
- Com Olímpia, começam no rio Grande, na foz do córrego do Porto Velho pelo qual sobem até sua cabeceira e vão em reta à barra do ribeirão do Piau, do rio Turvo.
- Com Palestina, começam na barra do ribeirão Piau, no rio Turvo e vão pelo Turvo abaixo, até sua confluência com o rio Preto.
- Com Tanabi, começam na confluência do rio Turvo com o rio Preto e vão por aquele abaixo até sua barra no rio Grande onde tiverem início estas divisas.
A primeira eleição municipal ocorreu em 5 de novembro de 1947, elegendo-se primeiro prefeito o fazendeiro Lourival Ribeiro de Mendonça, Fiico Ribeiro, que ficou no cargo até o final de 1949, quando renunciou e assumiu Clarismino Luiz Pereira.
