Em 1831, José Rodrigues da Silva, proprietário da Fazenda Cachoeira aliou-se aos irmãos João da Rocha e Lourenço da Rocha, novos donos de terras na localidade de Malhada do rio Trairi, povoado de Santa Rita da Cachoeira. A escolha do local para a implantação do núcleo populacional foi feita porque na localidade de Cachoeira não havia água suficiente para suprir as necessidades de uma população.
Logo, muitas casas surgiram, de forma alinhada, em torno da capela construída em homenagem a Santa Rita de Cássia, a qual José Rodrigues era devoto. O povoado foi mudando de nome com o passar dos anos. Depois de Santa Rita da Cachoeira, mudou para Santa Cruz da Ribeira do Trairi e por último, para Santa Cruz.
Há uma lenda que justifica a origem do vínculo de Cruz aos nomes dados ao lugar, contada em diversas versões pelos habitantes do município: um missionário, ouvindo falar que os habitantes das ribeiras do rio Trairi sofriam as inclemências das secas, bem como ataques de animais ferozes e que entre eles havia lutas e rivalidades, resolveu visitar o povoado. Chegando lá, mandou fazer uma grande cruz com os ramos de uma árvore chamada inharé. Em frente a capela, um enorme buraco foi aberto e o missionário ordenou que nele todos jogassem suas armas, cobrissem o buraco com terra e ali fincassem a cruz. Então, disse o missionário — “virá um padre, muito estimado, que mandará retirar esta cruz para um monte; não consintam, pois esta é a Santa Cruz do Inharé”. Contam ainda que a árvore inharé era sagrada e que atraía toda sorte de males quando seus ramos eram quebrados. Depois que o missionário ergueu a cruz de Inharé, os malefícios cessaram, as fontes jorraram água e os animais tornaram-se mansos. No ano de 1835, com o nome de Santa Cruz da Ribeira do Trairi, tornou-se distrito.
A luta para transformar o distrito em município contou com a participação fundamental do padre Antônio Rafael Gomes de Melo, do Tenente coronel Ivo Abdias Furtado de Mendonça e Menezes e dos fazendeiros Trajano José de Faria e Félix Antônio de Medeiros. Desmembrado do município de São José de Mipibu, no dia 11 de novembro de 1876, o distrito de Santa Cruz da Ribeira do Trairi, tornou-se município.
Em 1890, passou a ser chamado simplesmente de Santa Cruz.