Il teatro venne commissionato a Palladio dall'Accademia Olimpica di Vicenza, nata nel 1555 con finalità culturali e scientifiche, tra le quali la promozione dell'attività teatrale. Tra i membri fondatori dell'Accademia vi era lo stesso Palladio, che per essa progettò numerosi allestimenti scenici provvisori in vari luoghi della città, com'era d'uso all'epoca, fino a che nel 1579 l'Accademia ottenne dalla municipalità la concessione di un luogo adatto ove poter realizzare stabilmente un proprio teatro, all'interno delle prigioni vecchie del Castello del Territorio. Il contesto era una vecchia fortezza di impianto medievale, più volte rimaneggiata ed utilizzata nel tempo anche come prigione e polveriera prima del suo abbandono.
La costruzione del teatro iniziò nel 1580, lo stesso anno in cui Palladio morì, ma i lavori proseguirono sulla base dei suoi appunti, e furono conclusi nel 1584, limitatamente alla cavea completa di loggia e al proscenio. Si pose dunque il problema di realizzare la scena a prospettive, che era stata prevista fin dal principio dall'Accademia ma di cui Palladio non aveva lasciato un vero progetto. Venne quindi chiamato l'architetto vicentino Vincenzo Scamozzi, allievo di Palladio.
Scamozzi disegnò le scene lignee, di grande effetto per il loro illusionismo prospettico e la cura del dettaglio, appositamente per lo spettacolo inaugurale, apportando inoltre alcuni adattamenti e i necessari completamenti al progetto di Palladio. A Scamozzi vengono inoltre attribuite le contigue sale dell'Odèo e dell'Antiodèo, oltre che il portale d'ingresso originale.
Il teatro venne inaugurato il 3 marzo 1585 con la rappresentazione dell' Edipo re di Sofocle ed i cori di Andrea Gabrieli (ripresa nel 1997 per l'Accademia Olimpica di Vicenza con la regia di Gianfranco De Bosio. In questa e altre rare occasioni le scene (che rappresentano le sette vie della città di Tebe) furono illuminate con un originale e complesso sistema di illuminazione artificiale, ideato sempre da Scamozzi. Le scene, che erano state realizzate in legno e stucco per un uso temporaneo, non furono tuttavia mai rimosse e malgrado pericoli d'incendio e bombardamenti bellici si sono miracolosamente conservate fino ai giorni nostri.
Il teatro è tuttora sede di rappresentazioni e concerti ed è stato incluso nella lista dei patrimoni dell'umanità dell'UNESCO, come le altre opere palladiane a Vicenza.