El origen de las Cruces de Mayo está en conmemorar el hallazgo por parte de San Elena, madre del emperador Constantino, de la verdadera cruz de Jesucristo en su peregrinación a Jerusalén. Al tratarse de una fiesta relacionada con la pasión de Cristo, su Cruz, la fiesta en rito romano es de color rojo.
Ciertos autores enlazan la fiesta de La Cruz de Mayo con un origen pre-cristiano en el Árbol de Mayo o Palo de Mayo. El culto al árbol ha sido común en la religión europea y se ha dado, entre otros pueblos, en celtas, germanos, griegos, romanos y eslavos. En el Arbor Intrat romano se cortaba un pino, se engalanaba con guirnaldas violetas, cintas de lana y una imagen de Atis y se llevaba al templo de Cibeles. En la Francia medieval los campesinos ponían el 1 de mayo árboles decorados frente a las casas señoriales y las iglesias. La costumbre del árbol decorado se daba entre los eslavos a finales de abril.
Aunque en algunos momentos, esta costumbre fue prohibida por clérigos y nobles. En Inglaterra se dejó de hacer a lo largo del siglo XVII, debido a la Reforma protestante. La costumbre del árbol ha sido habitual en España celebrándose normalmente entre el 30 de abril y el 3 de mayo. En algunos lugares (sobre todo católicos) la costumbre del árbol pasó a ser el Mayo Florido o la Pascua Florida.
Las primeras celebraciones populares de la Cruz de Mayo son del siglo XVII. Lope de Vega escribió en su obra La mejor enamorada, la Magdalena una versión cristiana de la copla Este sí que es mayo famoso dedicada a la cruz de mayo:
Este sí que se lleva la gala
que es la Cruz en que Dios murió.
Este sí que se lleva la galaque los otros árboles no.
