O núcleo que deu origem ao atual Município foi uma vila de garimpeiros denominada Gameleira, no começo do século XX, e, a exemplo do que ocorre em “corridas do ouro”, teve, posteriormente, seu declínio. O mesmo fenômeno ocorreu com o povoado de Cajueiro. Nos vilarejos mais antigos como Gameleira, Santo Antônio e Cajueiro, Seus moradores viviam da extração do ouro e da madeira de lei, principalmente aroeira, hoje extinta na Região; de fazendas de gado bovino; de agricultura de subsistência, onde se destacava o cultivo de arroz; de caça para um comércio de peles de animais silvestres; e da pesca nos rios da região. Gameleira era pequeno povoado de garimpo de ouro. O Acesso nessa época era feito diretamente com Conceição do Araguaia, através de caminhos abertos nas florestas e nos serrados.
Por volta de 1920, houve um ataque, por parte dos índios Kaiapós, habitantes da região do Salobro, resultando no massacre dos moradores de Gameleira e Cajueiro, povoações próximas uma da outra. Dos poucos sobreviventes que conseguiram fugir, alguns voltaram e recomeçaram a vida do mesmo modo, reforçada naquela ocasião, pela extração do látex da havea brasiliensis.
Em 1972, com a abertura da então rodovia PA 150 (atual BR 158), tiveram início as vilas de Marajoara e Pau d’Arco. A vila Marajoara iniciou com a montagem da serraria Marajoara e a construção de casas para os operários. A vila Pau d’Arco também teve início com a construção da Serraria Pau d’Arco.
As povoações da região de Pau d’Arco tinham vida própria, independente da administração municipal centralizada na época em Conceição do Araguaia, e como a maioria dos municípios paraenses não dispunha de recursos suficientes para atender todos os núcleos populacionais sob sua jurisdição.
Com a emancipação política de Redenção, passando a ser município e ter prefeito eleito e câmara municipal a partir de 1983, Pau d’Arco agora passa a pertencer ao município recém formado.
O núcleo de Pau d’Arco prosperou, sobrepujando a povoação de Marajoara. Elevado à categoria de Município e Distrito com a denominação de Pau d’Arco, pela Lei Estadual nº 5.696, de 13 de dezembro de 1991, desmembrado de Redenção e instalado em 01 de janeiro de 1993.