La plantación del Mayo guarda relación con la mitología tradicional sobre árboles y bosques que se ha dado en el País vasco y en otros lugares de Europa desde tiempos remotos (ver el artículo Árboles sagrados en Euskal Herria). El antropólogo británico George Frazer, autor de La rama dorada, relaciona estas fiestas primaverales con una mentalidad mágico-animista que cree en la influencia del espíritu del árbol sobre el hombre, y también sobre las cosechas y los animales. "Traer de los bosques un pino adornado con violetas y tiras de lana es semejante a la costumbre popular moderna del árbol Mayo o árbol del Verano" (Frazer, 1890, 2006:408). Aquellos viejos rituales indogermánicos pasaron luego a la antigüedad clásica dando lugar por ejemplo a la fiesta de Attis (el 22 de marzo) en la que se colocaba un árbol cortado ante el templo de Cibeles. Finalmente, la mayoría de los pueblos europeos heredaron aquellas fiestas que serían asimiladas por el cristianismo.
En el norte peninsular, hay testimonios de la celebración del Mayo al menos desde el siglo XV. Florencio Idoate, en sus Rincones de la historia de Navarra, hace alusión a un proceso judicial de 1536, en el cual los mozos de Ostiz colocaron un mayo entre las casas de Garchotena y de Latasa, y después del acto ritual se dedicaron durante varias noches a recorrer las calles, celebrando "muchos juegos y placeres, andando y dando muchos golpes por las puertas". También hay documentos de la Cofradía de la Santa Cruz, en Cintruenigo, que acreditan su celebración en 1587.