The department store on the corner of Spálená and Národní streets was built on the site of the Neo-Gothic Šlik Palace, based on a design by Miroslav Masák, John Eisler, and Martin Rajniš from the Liberec-based SIAL studio, which was founded in 1968 by Karel Hubáček, the architect of the Ještěd transmitter. Máj opened its doors to customers on April 21, 1975. In 2006, the Ministry of Culture designated the building a cultural monument.

The monument-protected building reopened to the public on June 24, 2024, following approximately two years of renovations that cost 4.5 billion crowns. Across its nine floors, Máj features shops, restaurants, entertainment centers, and a rooftop observation deck. Even before its opening, two moving butterflies—several meters in size—by artist David Černý, with bodies resembling Spitfire fighter planes, sparked controversy on the façade of Máj. The interiors of the entertainment centers on the upper floors of the department store also drew criticism from some architects and segments of the public. Another controversy was sparked by the kitsch arcade park “Levels” on the upper floors of the building.