The Paramount opened at 713 Congress Avenue on October 11, 1915, as the Majestic Theatre, a vaudeville house built by Austin businessman Ernest Nalle on land his family had owned since 1885. The Chicago firm of John Eberson, John Reed Fugard and George Arnold Knapp drew the plans, J.F. Johnson built it, and Austin architect George Albert Endress supervised. Its 1976 National Register nomination puts the cost near $150,000 and the seating near 1,400. Harry Houdini played eight shows there, and the Majestic also ran silent films with orchestra or organ accompaniment. In 1930 the house was remodeled for sound, with upholstered seats, air conditioning and a blade sign, and it reopened on August 29 as the Paramount, named for its new owner, Paramount-Publix, with the Marx Brothers in Animal Crackers. Interstate Theatres, Karl Hoblitzelle's Texas circuit, operated it until 1975. During World War II the Paramount sold $8.4 million in war bonds. It hosted the world premiere of The Fabulous Texan, and on July 30, 1966, an estimated 30,000 people filled Congress Avenue for the world premiere of Batman. Under segregation, Black Austinites were barred or confined to the upper balcony; activists picketed the Paramount and State box offices before the theaters desegregated in the 1960s. By the 1970s ABC Interstate had stopped making repairs, and a Holiday Inn was planned for the site. Interstate closed the Paramount as a first-run house on April 10, 1975. John Bernardoni, Charles Eckerman and Stephen Scott took over the lease and reopened it on April 27 with Citizen Kane, paying the bills with cheap classic-film rentals. That program became the Paramount Summer Classic Film Series. The building was listed on the National Register on June 23, 1976, and became a Recorded Texas Historic Landmark the same year. Federal money, $1.85 million obtained with help from Congressman J.J. Pickle and Governor Dolph Briscoe, paid for 95 percent of a 1978–1980 restoration. The Best Little Whorehouse in Texas premiered there on July 11, 1982, with a parade on Congress Avenue, and Spy Kids had its Austin premiere there on March 24, 2001. Scenes for Richard Linklater's The Newton Boys and Waking Life were filmed in the auditorium, as was a post-credits concert in Spy Kids 2. In 2000 the Paramount merged with the State Theatre next door to form the Austin Theatre Alliance. It is a main venue for SXSW Film and the Austin Film Festival: I Love You, Man opened SXSW there in 2009, The Incredible Burt Wonderstone had its world premiere there in 2013, and Everything Everywhere All at Once opened the 2022 festival there. A replica of the 1930 blade sign was lit in September 2015 for the centennial. In November 2025 the Alliance announced a $65 million campaign to restore the Paramount, with the theater scheduled to close for about eight months starting in June 2026.