Designed by John Eberson under direction of Karl Hoblitzelle, the Majestic Theatre was constructed in 1920 as the flagship theater for Interstate Amusement Company, a chain of vaudeville houses.

The interior was originally divided into theater and office space, with 20,000 square feet (1,900 m2) of the upper four floors used as the headquarters of the Interstate Amusement Company.

The interior lobby and auditorium was of baroque design with decorative detailing consisting of Corinthian columns, egg-and-dart molding, cartouches, and Roman swags and fretwork.

Other features included an ornate cage elevator serving the two balconies, crystal chandeliers, brass mirrors, ferns, and a marble fountain.

The Melba, Tower, Palace, Rialto, Capitol, Telenews (newsreels and short-subjects exclusively), Fox (live burlesque), and Strand theatres were all demolished by the late 1970s; only the Majestic remains today.

The theatre began hosting movie premieres and associated stars such as Jimmy Stewart, Gregory Peck, and John Wayne.

The Hoblitzelle Foundation turned the Majestic Theater over to the City of Dallas in January 1976 and the theatre was restored for use as a performing arts center.