A região onde está situada Terra Nova foi ocupado por sesmarias doadas pela poderosa Casa da Torre (cuja família, Garcia D'Ávila acumulou o maior latifúndio brasileiro incluindo boa parte dos atuais estados da Bahia, do Sertão de Pernambuco, do Piauí e Cariri Cearense) ao fazendeiro Antonio Pereira da Costa. As lutas entre os sesmeiros e os grupos indígenas cariris misturados com grupos de origem tupi e africanos refugiados no litoral é recordado no nome de sítios como Contendas e Trincheira na fronteira do município com o vizinho Salgueiro, onde ainda hoje habitam descendentes de Antonio Pereira. Estes, de origem mestiça entre lavradores portugueses, indígenas e africanos, se misturaram com famílias de origem européia, provavelmente filhos de religiosos ou aventureiros como as famílias Callou e Arnoud, de origem francesa, com os descendentes de Manoel de Sá fundador de Salgueiro-PE, Antonio da Cruz Neves, autor do Massacre do Ouro Preto, que eliminou os índios da região e Francisco Magalhães Barreto e Sá, fundador de Barbalha-CE. Descendia destes grupos o Coronel Geremias Sá, sua mulher Joaquina Parente de Sá Barreto, "Branca", e seu filho Glicério de Sá Parente que lideraram a cidade na sua emancipação política e o também coronel Pereira Dum das Taíras, atual distrito de Guarani.

 

Os fazendeiros baianos e cearenses que ocuparam o município se dedicaram a pecuária extensiva, na chamada civilização do couro, vendido para o Cariri cearense e a região dos São Francisco. Contavam com escravos negros e agregados mestiços e índios conformados com o domínio desta aristocracia. Mais tarde, brancos pobres e ciganos chegaram ao território conquistando pequenas propriedades e se dedicando ao comércio. Dessa forma a população se dividiu em três classes, Famílias tradicionais de fazendeiros aparentados, brancos pobres e "cabras". Com o tempo, os negros conquistaram pequenos territórios, onde se dedicavam à agricultura de subsistência, formando verdadeiros quilombos, como Contendas, no município vizinho de Salgueiro - que foram trazidos para o local pelo "major" João Parente de Sá Barreto, primo de dona Branca - que conseguiu o 'status' de Comunidade Quilombola.

 

A influência política dos alferes e capitães-mores do período colonial foi substituído pelo coronelismo da República do Café com Leite. Os Pereiras e Sá Barretos se associaram aos Filgueiras Sampaios de Barbalha e Serrita, descendentes do Cristão-Novo português José Quezado Filgueiras Lima, pai do capitão-mor do Crato-CE, José Pereira Filgueiras e de Romão Pereira Filgueiras, cujos descendestes se uniram mais tarde a poderosa família Sampaio. Essa família dominou várias cidades da região como Barbalha-CE e Serrita-PE, e casaram-se com as famílias de Salgueiro e Terra Nova para estender sua influência a essa região. Glicério Parente aliou-se à Veremundo Soares de Salgueiro, desfrutando do prestígio deste coronel. Com o declínio das duas famílias, se aliaram aos Cabral e Freire de Parnamirim-PE e aos Coelhos de Petrolina-PE.

 

Em outra versão, mais conciliadora, uma das famílias pioneiras na colonização de Terra Nova-PE foi a de Gregório Pereira Pinto (Pereirinha) - filho do capitão Antonio Pereira Pinto e de Joana Batista do Espírito Santo - que com sua mulher Ana Angélica de Jesus - filha de Francisco Magalhães Barreto e Sá, fundador de Barbalha-CE - ainda no século XIX, adquiriu terras no que hoje é um município sertanejo. Seus filhos Zuza e Callou, suas filhas e outras famílias tradicionais que a eles se associaram, iniciaram o processo de desenvolvimento econômico, político e social do lugar. Tiveram o apoio dos remanescentes de índios sobreviventes dos conflitos com os sertanistas e donatários no século XVIII - os nomes das fazendas Contendas e Trincheira, na fronteira com a vizinha Salgueiro, devem ser lembrança destes conflitos – e africanos fugidos de quilombos arrasados que aqui receberam terras e prosperaram, preservando suas culturas sob a proteção destes fazendeiros. Muitos outros brancos vieram depois, adquiriram terras ou se dedicaram ao comércio. Descendem deste Pereirinha os Parentes, os Sá Barretos e os Callous. Entre seus descendentes destacaram-se Glicério de Sá Parente e sua esposa Adélia de Sá Barreto, que lideraram o processo de emancipação política do município. Também foi seu descendente o coronel Pereira Dum do Guarani. Sua família associou-se aos Sá Araújo de Salgueiro e aos Filgueiras e Grangeiros do Cariri entre outras famílias da região.

 

Enquanto distrito, Terra Nova foi criada com sede na povoação de Pau Ferro, por Lei municipal de nº 03, de 13 de março de 1893. Na época, integrava o território do município de Leopoldina, hoje Parnamirim. A 11 de novembro de 1904, a sede do distrito foi transferida para a povoação de Mocambo, passando, a 19 de janeiro de 1911, para a localidade de Terra Nova.

 

Com a extinção do município de Leopoldina, o distrito de Terra Nova passou a integrar o município de Serrinha (hoje Serrita). Depois, o município foi restaurado e Terra Nova voltou a integrar o seu território. O município de Terra Nova foi criado a 31 de dezembro de 1958.