Aunque varios historiadores han querido identificar a Santa Cruz de la Zarza con el nombre de algunos enclaves romanos o visigodos, lo cierto es que no hay constancia de población en el solar del municipio anterior a la Alta Edad Media.
El nombre de Santa Cruz se documenta por vez primera en 1210, en un documento en el que el Obispo de Cuenca, don García, dona al Cabildo de la Catedral los derechos de varias iglesias: Damus et concedimus ecclesias de La Sarça, et de Sancta Cruz et de Belmont ad usus similiter eiusdem refectorii.
Se trata de un topónimo común de la época de la repoblación tras la conquista de estas tierras a los musulmanes, que alude a la Cruz como emblema de la Orden de Santiago (fundadora del pueblo), y que podemos rastrear en las palabras de López Agurleta, cronista del fundador de dicha Orden D. Pedro Fernández: Recibió la Cruz de su espada, y sus trabajos, para trepar desde la corriente de las aguas a la cumbre. Trepó en fin desde el tajo á lo más alto, entre Aurelia, y Alharilla, y colocó allí el Estandarte de la Santa Cruz.
El apellido de Zarza, hace sin duda alusión a la abundancia que hubo de estas plantas en la comarca en la que se ubica Santa Cruz, forma toponímica propia de la época de la repoblación posterior a la Reconquista que suele utilizar nombres de plantas: ajo (Ajofrín), cebolla (Cebolla), almendro (Almendros), peral (Perales de Tajuña, Perales del Río...), etc. El propio López Agurleta lo justifica como apelativo para evitar confusiones con otros lugares de nombre similar: De la villa y castillos de Santa Cruz en tierra de Cáceres no debe dudarse, que siendo señor, ó poblador el Maestre, la dio este nombre, como en su estado de Humanes, termino de Hita, á otro lugar, llamado allí Santa Cruz. Y esto mismo entre Aurelia, y Alharilla, la Villa de Santa Cruz, que para distinción de otras, y no porque la Zarza fuese antes Lugar de Termino, ni nombre, llaman comúnmente Santa Cruz de la Zarza.
Existe otro topónimo Santa Cruz de la Zarza en el municipio de Ribas de Campos, en tierras palentinas. Se trata de una iglesia románica construida a comienzos del siglo XIII por la Orden de los Premonstratenses (Mostenses), que heredaron el lugar en 1176, cedido por la Orden de Santiago que lo tenía anteriormente por concesión de Alfonso VIII. Desconocemos la relación de este templo con la de nuestro municipio.
Los habitantes del municipio ostentan el gentilicio de santacrucero/santacrucera o santacruceño/santacruceña, aunque este último no se utiliza.