A cidade tem suas raízes históricas no distrito de em Conceição de Monte Alegre, fundado por José Teodoro de Sousa, que fez doação, em 1873, de uma área de 193 hectares para a fundação de um novo patrimônio. Na época, a região já era habitada por três etnias indígenas: caiouás, xavantes e caingangues. Estes últimos ofereceram grande resistência à invasão de seus territórios pelos novos colonizadores, em sua maioria mineiros que fugiam ao alistamento militar compulsório para a Guerra do Paraguai.

Em 1891, Conceição de Monte Alegre foi elevada à categoria de distrito, cujo território se estendia entre o rio Paranapanema e rio do Peixe, até as barrancas do rio Paraná. Os primeiros habitantes não índios da região foram José Teodoro Filho, Manuel Pereira Alvim e José Antônio de Paiva, os quais se instalaram nas margens do ribeirão Alegre e do rio São Mateus. A origem da atual cidade remonta ao núcleo urbano de Moita Bonita. A princípio, era apenas um ponto de referência ao longo do ribeirão Alegre, composto por um pequeno bosque a 400 metros abaixo da atual estação ferroviária.

Com a criação do ramal ferroviário pela Sorocabana, em 23 de março de 1916, a estação recebeu o nome de “Paraguaçu”, denominação que a cidade, formada posteriormente, adotou. Em 1930, a companhia ferroviária Sorocabana mudou o nome da estação para “Presidente Washington”, para distingui-la de outras cidades com o mesmo nome e para homenagear o então presidente brasileiro Washington Luís, porém o novo nome não foi aceito pela população e o antigo nome, Paraguaçu, retornou no ano seguinte.

Em 1941, o presidente brasileiro Getúlio Vargas determinou que, a partir de 1 de janeiro de 1945, não houvesse, no Brasil, cidades com nomes iguais. Como resultado, em 22 de setembro de 1943, o prefeito da época, Antenor Assunção, reuniu representantes do comércio, lavoura, indústria e profissionais liberais (vinte no total) com a finalidade de sugerir, à Comissão Estadual, um novo nome para Paraguaçu, de modo a diferenciá-la do município homônimo no estado de Minas Gerais. Assim, foram propostos, pela ordem de preferência, os seguintes nomes: Araguaçu, Caramuru, Atlanta, Pauliceia, Guaçupará, Guaçulândia, Paguaçu e Mirante.

A comissão então criada oficializou o nome “Araguaçu”, que vigorou de 1 de janeiro de 1945 a 31 de dezembro de 1949. Em 1 de janeiro de 1950, ocorreu nova mudança e o nome da cidade passou a ser o atual: Paraguaçu Paulista. O tráfego ferroviário foi aberto em 1916, possibilitando maior desenvolvimento na agricultura, com expansão de novas áreas agrícolas, o que provocou aumento demográfico. Em 18 de dezembro de 1923, foi criada a Vila Paraguaçu, elevada a categoria de distrito de Conceição de Monte Alegre.

Em 30 de dezembro de 1924, tornou-se município (unidade político-administrativa independente), tendo sido instalado em 12 de março de 1925. Em 1948, teve a sua organização político-administrativa definida com a criação do distrito-sede de Paraguaçu Paulista. Em 5 de março de 1997, Paraguaçu Paulista foi transformada em estância turística.

Topônimo
De acordo com o dicionário de tupi-guarani de Gumercindo Saraiva Rodrigues Alves Pereira de Carvalho, “Paraguaçu” significa “mar grande”, “rio grande”. O nome é formado pela junção de pará (mar, rio grande) e gûasu (grande)[10]. O termo “Paulista” serve para distinguir o município do município homônimo no estado de Minas Gerais.