Originally named the Star Theater, it was built in 1912 to show silent movies to the African American community that had taken up residence around 18th & Vine in the then legally-segregated Kansas City.  It was renamed the Gem Theater in 1913. By 1929, when the theater began to show talking movies, the Gem became a fixture on 18th Street as the major movie theater open to African American audiences.
In 1960 the Gem Theater no longer showed films and began to fall into disrepair. As one of the most notable buildings to survive the industrialization and redevelopment of the district in the 1960s and 1970s, the theater became a centerpiece of plans to revitalize the Jazz District and figured prominently in the district's application for status as a historic district in 1991. 
When the Gem was still playing movies, up until 1960, the seating capacity was 1,414, but after renovations capacity was cut to 500 seats. Indeed, virtually all that remains of the original theater is the facade, which dates to an early renovation in 1923. After the renovations of the 1990s, the Gem Theater opened for live performances in 1997. Like the American Jazz Museum across the street, the Gem is owned by the city government.  Renovations were spearheaded by Patricia Jordan, who is now president of what has become the Gem Theater Cultural and Performing Arts Center. 
Interestingly, the redevelopment and restoration of the Gem Theater and surrounding Jazz District was sparked in no small part by a movie: Robert Altman's 1996 Kansas City, which was shot on location. Given the destruction of many of the buildings in the district, and the disrepair into which the surviving ones had fallen, Altman's movie required the extensive use of facades to restore the appearance of 18th & Vine as it would have looked in the 1930s, when the film is set. The facades made the rich artistic and cultural history of the district immediately visible, and the film's release coincided with a wave of investment that sought to redevelop the district and restore at least part of the area's former vibrancy.