Kazalište Ulysses utemeljili su glumac i redatelj Rade Šerbedžija i pisac Borislav Vujčić. 2001. godine, slavna britanska filmska i kazališna glumica Vanessa Redgrave, uz sudjelovanje Mostarske sinfoniete, svečano ga je otvorila dobrotvornim koncertom.
Prva je predstava bila Shakespeareov Kralj Lear, u režiji Lenke Udovički, s Radom Šerbedžijom u naslovnoj ulozi. Mali producentski tim, pod vodstvom Tatjane Aćimović, upustio se u provođenje u djelo jedne zanesenjačke ideje o kazalištu na gotovo pustom otoku, ne sluteći da će predstava koju su 2001. podigli na noge steći kultni status među publikom, da će se izvoditi iz godine u godinu, a da će eksperiment jednog ljeta prerasti u redoviti ljetni festival, svake godine sa sve više predstava i kulturnih događanja.
Predstava Kralj Lear igra i dalje. Nekoliko lokacija unutar autro-ugarske pomorske tvrđave Minor na Malom Brijunu poslužile su za prirodni dekor koji oduševljava publiku iz cijelog svijeta već dvanaest godina, a okupila je umjetnike iz Hrvatske, Slovenije, Bosne i Hercegovine, Srbije, Velike Britanije, SAD-a i Ukrajine.
Tijekom godina Kazalište Ulysses nastavilo je razvijati svoj specifični kazališni izraz – spajanje velikih djela svjetske dramske literature, poput Euripidove Medeje, s Mirom Furlan i Aleksandrom Cvjetkovićem u glavnim ulogama i Weissove drame Marat/Sade, s Radom Šerbedžijom i Zlatkom Vitezom, s jedinstvenim otvorenim prostorom bivše vojne tvrđave Minor te međusobno povezivanje, nakon duge stanke, umjetnika iz regije i pozivanje, svake godine, novih, inspirativnih umjetnika iz cijeloga svijeta.