Obchodní dům na rohu Spálené a Národní vznikl na místě novogotického Šlikova paláce podle návrhu Miroslava Masáka, Johna Eislera a Martina Rajniše z libereckého ateliéru SIAL, který v roce 1968 založil autor ještědského vysílače Karel Hubáček. Máj se zákazníkům otevřel 21. dubna 1975. V roce 2006 prohlásilo ministerstvo kultury dům kulturní památkou.

Veřejnosti se památkově chráněná budova otevřela po zhruba dvouleté opravě 24. června 2024, stála 4,5 miliardy korun. V devíti patrech nabízí Máj obchody, restaurace, zábavní centra či střešní vyhlídkovou terasu. Ještě před otevřením vyvolali kontroverze dva několikametrové pohybující se motýli od výtvarníka Davida Černého s trupem napodobujícím stíhačku spitfire na fasádě Máje. Kritiku některých architektů i části veřejnosti sklidily i interiéry zábavních center v horních patrech obchodního domu.