Interstate Theatres opened the Alabama on November 2, 1939, at Shepherd Drive and West Alabama, a few weeks before the River Oaks Theatre opened nearby on West Gray. It was the chain's tenth theater in Houston and the first and largest of four Houston theaters that opened that November. The first feature was Man About Town with Jack Benny. The Art Moderne house held about 1,130 seats, and a shopping center planned around it was eventually built. Houston film historian David Welling calls the Alabama the best surviving example of Interstate's theater architecture from that period.
For more than four decades the Alabama ran first-run films. Lawrence of Arabia opened there on April 4, 1963, and ran 21 weeks. The Sound of Music opened on March 31, 1965, and ran 90 weeks. Lines wrapped around the building for Close Encounters of the Third Kind in 1977, Alien in 1979, and The Empire Strikes Back the following year. Competition from multiplexes, cable, and home video cut into attendance, and the movie era ended in early December 1983 with the horror film Mortuary.
In 1984 the Austin-based chain Bookstop restored the auditorium and reopened it as a bookstore, keeping the screen in place. Houstonia's history columnist later called it the best example of historic preservation and adaptive reuse in Houston. Weingarten Realty bought the surrounding Alabama Shepherd Shopping Center in 2004 and considered tearing the theater down for a high-rise, and Preservation Texas put it on its 2007 Most Endangered Places list. The bookstore, by then run by Barnes & Noble, closed on September 15, 2009. In 2011 the interior was partly gutted and the sloped floor leveled for a Trader Joe's grocery, which opened in September 2012. The Houston Archaeological and Historical Commission approved the changes, and the store restored a turquoise Art Deco ceiling medallion from the theater. Preservation Texas now lists the building as saved.