Cruz Herrera's grandparents originally lived in Cádiz, where they operated a lithographic press. Their skills were in demand in British-ruled Gibraltar, where snuff was manufactured and sold in envelopes. To meet the demand for printed envelopes and packaging labels, they moved their press to Gibraltar. They were unable to live there, as it required special permission, so they settled in the Spanish-ruled town of La Línea de la Concepción on the border with Gibraltar and walked across the frontier each day to operate their press. In 1889, Cruz Herrera's father, José de la Cruz Garcia, married a local woman – 19-year-old Antonia Herrera Ramírez, the niece of La Línea's first mayor – and was himself mayor of the town for a short time. Eight months later on 1 October 1890, Cruz Herrera was born as the first of seven children and was named after his grandfather, who like his father was also named José. He was given the birthname of José Maria Remigio.