La costruzione del Politeama Petruzzelli fu lunga e articolata, dettata dalla volontà di creare un luogo di divertissement per un ampio numero di cittadini. Il 29 ottobre del 1879, il Consiglio Comunale decise di offrire un suolo in corso Cavour – vicino alla nascente Camera di Commercio – a chi avesse costruito un edificio per spettacoli in grado di contenere 3.000 persone. Il progetto fu accantonato a causa della crisi economica e solo il 31 marzo 1892, il Consiglio Comunale tornò a discutere del Politeama. L'11 gennaio 1894 pervennero al Comune varie proposte, fra cui quelle di Donato Greco, Giacomo Sbisà, Antonio Petruzzelli e il fratello Onofrio. Tutte le proposte prevedevano però un politeama provvisorio, parte in muratura, parte in legno, per cui furono rifiutate dal Comune. I fratelli Petruzzelli presentarono allora un nuovo progetto realizzato dall’ingegnere bitontino Angelo Cicciomessere (poi Messeni), marito della loro sorella Maria. La nuova proposta, che prevedeva un politeama in muratura sbaragliò il campo dagli avversari.
I due fratelli chiesero e ottennero di denominare il teatro Politeama Petruzzelli che il 14 febbraio del 1903 venne inaugurato con Gli Ugonotti di Meyerbeer. Dal punto di vista architettonico il teatro è da considerarsi un teatro “all’italiana”, un tipo di struttura particolarmente diffusa in Italia tra il XVIII e XIX secolo, con alcune influenze del teatro “alla francese”. Del teatro “all’italiana” presenta la forma a ferro di cavallo e i palchi tra loro separati e divisi in altezza per ordini. L’ampia platea consente una visibilità ottimale dello spettacolo. La scena ha una profondità tale da consentire l’utilizzo dell’elemento innovativo delle quinte prospettiche che consentono all’attore di recitare dentro e non davanti alla scena, come invece avveniva solitamente nel teatro rinascimentale. Al teatro “alla francese” si ispirano la resa delle gallerie, la cupola semisferica e la ricchezza degli spazi annessi. Il foyer, ad esempio, è un’area molto ampia dalle ricche decorazioni, pensato soprattutto per eventi mondani o comunque per un uso diverso da quello delle rappresentazioni teatrali. La sala del politeama presenta due ordini di palchi completi, ai quali si aggiungono altri due ordini composti da palchi laterali e gallerie centrali. La decorazione pittorica della volta – così come quella del soffitto del foyer – venne realizzata da Raffaele Armenise, divisa in quattro sezioni da palmizi disposti a ventaglio su basamenti a fioriere rilevate. Il soffitto, così come il sipario e parte delle strutture e decorazioni del teatro andarono distrutte nel devastante incendio del 1991. Nel 2009, con la riapertura del Petruzzelli – ricostruito con strutture all'avanguardia per sicurezza e tecnologia, esattamente com’era nei suoi spazi fondamentali – l’attività artistico-culturale della Fondazione lirico sinfonica Petruzzelli ha ritrovato il suo palcoscenico naturale.