The theater was originally built in 1918 for Henry Miller, an actor, producer, manager, and sometime playwright, whose name is still visible on the theater’s facade.

Born in London, Miller came to New York in 1917 and decided to build a theater for himself. He hired architects Ingalls & Hoffman, and his friend Paul Allen to work with them. They designed the exterior to mimic an eighteenth-century New England building. After Miller’s death in 1926, his family continued to operate the theater until 1968, at which time it was sold. In the ensuing years it became a pornography theater and later converted into a night club. In 1998, it was reopened as a legitimate theater only to close again in 2004 when the interior was completely demolished to make way for an office tower. It was rebuilt by the firm of Cook + Fox below ground as a state-of-the-art venue, maintaining the original landmarked facade. On March 10, 2010, composer and lyricist Stephen Sondheim’s eightieth birthday, the theater was renamed in his honor.