Early in his career, Connolly auditioned for the Metropolitan Opera Company and performed in Gilbert and Sullivan in repertory. He made his Broadway debut in 1977 in Harold Pinter's Otherwise Engaged, understudying the role of Stephen Hench (a part he continued on tour). He followed it with the Ira Levin comedy Break a Leg (1979) and Tennessee Williams' Clothes for a Summer Hotel (1980).
In musicals, he spent a year in the national touring company of Annie (as Bert Healy) and played the sinister Mr. Murdstone in the 1981 Broadway show Copperfield. In the 1982 off-Broadway play Booth, he played Junius Booth and Secretary of War Edwin Stanton opposite John Glover as John Wilkes Booth.