История Омского государственного театра куклы, актера, маски «Арлекин» началась в апреле 1936 года, когда группа энтузиастов организовала в городе детский театр. Первые репетиции проходили в подвалах Омского драматического театра, а дебютный спектакль — чеховская «Каштанка» — был показан под открытым небом в июле того же года. Кукол для первых постановок привезли из московского театра Сергея Образцова.

Свое нынешнее название — «Арлекин» — театр получил в 1995 году. В декабре 2005 года театр переехал в новое современное здание, которое считается одним из лучших в России для кукольных театров. Пятиэтажное здание из прозрачного стекла, возведённое в рекордные сроки (чуть более года), называют «дворцом». Интерьеры богато украшены художественной резьбой по дереву с изображениями сказочных сюжетов, что создаёт атмосферу погружения в сказку ещё до начала спектакля.

В 2006 году театру исполнилось 70 лет. С этим юбилеем связано издание книги по истории театра «Новые времена». Книга рассказывает об истории коллектива и его «новом времени», связанном с переездом в современное здание на проспекте Маркса.

В ней содержатся:

Технические возможности здания позволяют «Арлекину» принимать крупнейшие мировые коллективы. Здание театра официально признано одним из ключевых брендов города и региона. С 2009 года здесь проходит международный фестиваль «В гостях у "Арлекина"», который в 2026 году вновь соберет театры из России, Ирана, Ливана и других стран.