William Fox hired Thomas W. Lamb, one of the foremost theater architects in America, to design a building that would serve as both a 2,500-seat theater and a second-floor ballroom accommodating 200 seated guests. Lamb, who would later design the nearby eclectic United Palace, believed in the theatrical power of ornament and color. The Audubon's facade presented terra-cotta glazed polychromy, encrustations, and cornices, a visual exuberance that announced the building's purpose before anyone stepped inside. Over the decades, the theater cycled through identities: the William Fox Audubon Theatre, the Beverly Hills Theater, the San Juan Theater. It served as a vaudeville house, a movie palace, and a meeting hall where political activists and trade unions, including the Municipal Transit Workers and the Transport Workers' Union, gathered in its rooms.

Malcolm X had been receiving death threats for months. His break with the Nation of Islam had made him a target, and his home had been firebombed just a week earlier. On that Sunday afternoon, he stepped to the podium in the Audubon Ballroom's second-floor meeting hall to address the Organization of Afro-American Unity. Moments after he greeted the audience, a disturbance broke out in the crowd. Then gunfire. Malcolm X was struck multiple times and died shortly after at Columbia Presbyterian Hospital, just blocks away. He was 39 years old. Three men were convicted of the murder, though the case remained contested for decades. Two of the convicted men were exonerated in 2021, more than half a century after the killing. The ballroom where he fell became one of the most significant sites in the history of the American civil rights movement.

By the late 1980s, the building had deteriorated, and Columbia University proposed demolishing it to build a biomedical research center. Preservationists and community activists fought to save the site, but they could not persuade the New York City Landmarks Preservation Commission to hold a hearing on granting the building landmark status. A compromise was reached through a public-private partnership between Columbia University Medical Center and the New York state and city governments. Most of the building was demolished starting in 1992, but two-thirds of the original facade, the portion along Broadway and West 165th Street, was preserved and restored. A section of the interior ballroom where Malcolm X was killed was also restored and protected for use as a memorial.

In 2005, the Malcolm X and Dr. Betty Shabazz Memorial and Educational Center opened in the preserved lobby, commemorating Malcolm X's contributions to the civil rights movement. The building behind the old facade is now the Audubon Business and Technology Center, part of Columbia University's Audubon Research Park. The architecture firm Davis Brody Bond designed Columbia's new structure, while preservation specialist Jan Hird Pokorny handled the facade restoration. Neptune still rides his ship above the entrance. The foxes still watch from between the windows. The building exists in two registers simultaneously: a whimsical theater where William Fox entertained early twentieth-century Manhattan, and a place of profound loss where a movement lost one of its most electrifying voices. Both histories are visible from the sidewalk, pressed into the same glazed terra-cotta.