Kazalište Ulysses su osnovali 2001. glumac i redatelj Rade Šerbedžija i dramatičar Borislav Vujčić. Svojim imenom ono je hommage Jamesu Joyceu, književniku čija biografija i djelo svjedoče o nazočnosti na Brijunima.
Prve predstava Ulyssesa na Brijunima bila je Shakespearov Kralj Lear, a koja se reprizira svih narednih sezona i postaje zaštitni znak ovog kazališta. Godinu dana kasnije izvedena je Euripidova Medeja sa Mirom Furlan u naslovnoj ulozi što izaziva veliki medijski interes. 2003. postavljaju predstavu Marat Sade. Play Beckett uprizoren je 2004., a Hamlet 2005. Pandurov Tesla Electric Company bio je na sceni 2006. Čak dvije su predstave izvedene 2007., i to Balade Petrice Kerempuha i Pijana noć 1918., a dvije su bile na repertoaru i godinu kasnije: Kaligula te Romeo i Julija '68, dok je 2009. na programu bio Don Juan u režiji proslavljenog Paola Magellia. Svoju jubilarnu, desetu sezonu, obilježili su postavljanjem Shakespearove Oluje. U prvih deset godina kazališta najviše je predstava režirala Lenka Udovički, a dvije je režirao Tomaž Pandur. 2011. godine postavljena je predstava Cabaret Brecht - Zadrživi uspon Artura Ulija sa sjajnom mlađom glumačkom ekipom koju je predvodio Ozren Grabarić u naslovnoj ulozi. 2012. godine postavljaju Odiseju Gorana Stefanovskog i dramu Pokojnik Branislava Nušića. Te je godine Kazalište Ullysses u pravom smislu postao središte regionalnog kazališnog života, te su u obje predstave igrale najveće zvijezde ovih prostora kao što su Jelisaveta Seka Sablić, Zijah Sokolović, Nikola Ristanovski, Jasna Đuričić, Anita Mančić, te Ozren Grabarić koji je briljirao u naslovnoj ulozi Odiseja.