The theater was named for the Keith-Albee-Orpheum circuit - the premier vaudeville touring network of the 1920s, founded by B. F. Keith and Edward Albee. The circuit operated in major American cities along the East Coast and in the Midwest, sending the era's biggest vaudeville stars from city to city on coordinated tours. Building a Keith-Albee theater in Huntington put the city on that circuit. Audiences who came to the new theater in 1928 could expect performances by artists they had read about in trade magazines, not just second-tier touring shows. The decision to give the theater the Keith-Albee name was both honorific and commercial - it signaled which league Huntington was now playing in.

Thomas W. Lamb was the dominant theater architect of the American movie palace era. His firm designed the Loew's State Theatre and the Ziegfeld Theatre in New York, the Loew's Penn in Pittsburgh, and roughly 150 other theaters across the country and beyond. For Huntington, Lamb worked in New Spanish Baroque style - a decorative idiom that referenced colonial Mexican and Spanish church architecture with elaborate plasterwork, dramatic vertical interior masses, and intense ornamentation around the proscenium. The lobby spaces were almost as elaborate as the auditorium. Cosmetic rooms, smoking rooms, and fireplaces in the men's and women's restrooms gave the theater the air of a cosmopolitan urban institution dropped into a small West Virginia city. The contrast was the point. Going to the Keith-Albee was meant to feel like an event.

The original Keith-Albee Wurlitzer organ was designed to accompany both live performances and the silent films that still dominated movie theaters in 1928. The instrument could produce nearly any sound effect required - horse hoofbeats, train whistles, gunfire, weather - and a skilled organist could improvise dramatic underscoring for the action on screen. The organ was removed and sold in the 1950s as live musical accompaniment lost its place in cinema. For decades the Keith-Albee operated without one. In 2001, after years of effort by Huntington native Robert Edmunds and his Huntington Theatre Organ Project, a 1927 Wurlitzer organ was purchased from another source and reinstalled in the Keith-Albee. The theater's original sonic vocabulary was restored, fifty years after the silence began.

By the 1960s and 1970s, the rise of television and the spread of suburban multiplexes had hurt the Keith-Albee's business as a single-screen movie theater. The Hyman family, who had owned the theater since 1928, adapted by dividing the main auditorium into three movie theaters. Two smaller screens were built into the east and west sections of the main hall. A fourth screen was later added in a street-facing retail space that has since become a screening room. The division saved the building's economic viability for several more decades, even as it compromised the architectural unity of Lamb's original design. The Keith-Albee ended its run as a functioning movie theater in 2006. The Hyman family donated the building to the Marshall University Foundation, which passed it to the Keith-Albee Performing Arts Center Foundation that operates it today.

In December 2006, the Keith-Albee hosted the world premiere of We Are Marshall, the film about the November 1970 plane crash that killed 75 people - the entire Marshall football team, coaches, fans, and crew - on a flight returning from a game in Greenville, North Carolina. The film starred Matthew McConaughey and Matthew Fox. The decision to hold the premiere at the Keith-Albee placed the city's most distinguished theater at the center of one of its most distinguishing tragedies. The 3,000-seat auditorium - even in its divided 2006 configuration - was the most fitting venue in town for an event that mattered to Marshall and to Huntington in deep, complicated ways. Today the theater hosts a regular schedule of Broadway tours, concerts, and the Marshall Artists Series.