Em 1829, dois frades capuchinhos que andavam em peregrinação passaram numa localidade chamada Gentil e aí se abrigaram debaixo de um juazeiro, onde permaneceram cerca de um mês. Durante esse período recebiam a visita de famílias das redondezas e praticavam atos religiosos como missa, confissões, orações etc. Ao se despedirem, deixaram no local uma grande cruz de madeira que seria a protetora dos moradores de Gentil.

Nessa localidade havia um rico fazendeiro chamado José Correia, dono de muitas terras e escravos. Algum tempo após os frades terem deixado Gentil, alguns vaqueiros que trabalhavam para José Correia, procurando gado pela caatinga deserta, passaram perto do local onde tinham se abrigado os capuchinhos e avistaram a grande cruz no dia 3 de maio de 1829. A cruz foi levada para a fazenda e colocada em sua capela. Muitas pessoas doentes, acreditando no milagre da cruz, começaram a fazer promessas. Algumas casas foram construídas e foi se formando uma vila.

A partir daí, começaram a festejar com atos religiosos a “Venerada Santa Cruz“, com muitas comemorações nos dias 1°, 2 e 3 de maio. Com o dinheiro arrecadado com essas festas, foi construído o Açude da Venerada, próximo à vila. O distrito de Santa Cruz foi criado pela Lei Municipal n° 51, de 23 de janeiro de 1915, subordinado ao município de Ouricuri.

Pelo Decreto-lei Estadual n° 92, de 31 de março de 1938, o distrito de Santa Cruz passou a denominar-se Vera Cruz. Em 31 de dezembro de 1943, pelo Decreto-lei Estadual n° 952, o distrito sofreu nova alteração toponímica, para Cruz de Malta. De acordo com a Lei Complementar n° 1, de 12 de julho de 1990, a Lei Estadual n° 10.623, de 1° de outubro de 1991, criou o município de Santa Cruz, desmembrado de Ouricuri, com sede no antigo distrito que voltou a denominar-se Santa Cruz. Foi instalado em 1° de janeiro de 1993.