Il teatro prende il nome da Gaetano Storchi, un ricco commerciante modenese che ne finanziò la costruzione. Sorge su un terreno della nuova area edificabile ricavata con la costruzione della barriera Garibaldi (1884), a seguito dell'abbattimento di porta Bologna (1882). L'ubicazione del teatro influenzò la singolare originale struttura dell'edificio, che presenta una doppia facciata: a settentrione si trova la facciata principale, che guarda su piazza Garibaldi, mentre quella da lato ovest si affaccia su viale Martiri della Libertà, un tempo il passeggio delle mura, ed è opera dell'architetto Maestri.

L'edificio è nato sulla base di un progetto particolarmente ricercato, che prevedeva locali di servizio, ridotto, fumoir, caffè; tuttavia, la realizzazione avvenne in economia, su un terreno che apparve instabile fin dall'inizio, e soprattutto con l'impiego di materiali scadenti che ne compromisero ben presto la stabilità. A ciò si devono i numerosi successivi interventi di ristrutturazione e recupero dell'edificio. Tra i più rilevanti, si ricordano il rifacimento della copertura e la modifica della curvatura della sala ad opera dell'ingegnere Luigi Sfondrini di Milano; il restauro dell'esterno con rifacimento dell'intonaco e delle cornici del 1929, e un successivo intervento sulla sala nel 1931.