Первым монументальным сооружением советского Омска стал памятник Борцам Революции работы Н. Н. Виноградова.

12 ноября 1919 года в овраге загородной рощи колчаковцы расстреляли 120 политзаключенных. Среди них были члены Омской подпольной большевистской организации и подозреваемые в сочувствии большевикам. В воскресенье, 30 ноября, в Омске состоялись всенародные похороны жертв белого террора. Местом их вечного упокоения была выбрана площадь перед Домом Республики. Ко дню похорон у братской могилы был установлен временный монумент в виде большой деревянной колонны с текстами революционной клятвы.

Идея создания постоянного памятника возникла сразу же после освобождения Омска. Сотрудники художественной секции культпросвета 5-й Армии исполнили эскиз памятника на братскую могилу и в январе 1920 года преподнесли его в подарок губревкому. В начале марта 1920 года скульптор И. Д. Шадр, которому было поручено выполнение работ по его сооружению, представил в губревком смету на 3 68375 рублей. Из-за отсутствия средств проект не был реализован. В апреле 1923 года на заседании президиума губисполкома было принято решение «О возложении ответственности за постройку памятника «Парижской коммуны» на скульптора Виноградова». По замыслу Н. Н. Виноградова, памятник на братской могиле должен был воплотить идею преемственности первой пролетарской революции и революции в России.

Скульптор работал над монументом без предварительного изготовления макета, сразу ставя каркас и нанося на него раствор. В качестве вяжущего средства использовался портландцемент, в который замешивалась мраморная крошка. Эта масса набрасывалась на «остов», форма моделировалась тут же, пока цемент не окаменеет. Такой способ лепки, хотя и привел к некоторой упрощенности скульптурных форм, но, вместе с тем, вся группа была эмоциональна и передавала дух революционной романтики того периода. Арматура фигур и знамени крепилась к арматуре стены, в которой была заложена основная ось всего сооружения. Каркас фигур делали рабочие, а конструкцию для лица и рук «вязал» сам художник. Работа с цементом требовала быстроты. Бригада рабочих и помощники скульптора с энтузиастом трудились не только днем, но и ночами. Для удобства работы был возведен деревянный шатер.

Скульптурная группа представляет собой женщину, в ее правой руке – знамя, левой она поддерживает раненого рабочего. Постамент памятника в виде усеченной пирамиды выложен из четырех рядов крупных гранитных камней. Высота скульптурной группы – 1,8 метра, высота постамента – 2,8 метра.

По версии краеведа И. П. Шихатова, за основу своего памятника Н. Н. Виноградов взял сюжет из проекта французского скульптора Бертеля, разработанного по заказу жителей города Лиможа в память о трагической гибели президента Франции Сади Карно. Но «…если у Бертеля фигура женщины олицетворяет республиканскую Францию, то у Виноградова – революционную Россию, поднявшую знамя Парижской коммуны, пронесшую его до победы и создания государства рабочих, а фигура мужчины – собирательный образ, олицетворяющий собой расстрелянную Парижскую коммуну, идеи которой не погибли, и обрели новую Родину». Идея преемственности двух революций отчетливо прослеживалась и в надписях, изначально имевшихся на постаменте памятника. Одна из них гласила: «Коммунары Парижа! У вас вырвали Красное Знамя, рабочие России отняли его и победили!». Вместе с тем другая надпись говорила о том, что памятник имеет непосредственное отношение к событиям местной истории: «Славным коммунарам Всероссийской коммуны, расстрелянным Колчаком в ноябре 1919 года». Впоследствии содержание надписей менялось.

Открытие памятника состоялось на торжественном митинге 15 июля 1923 года. В настоящее время он является неотъемлемой частью мемориального сквера «Памяти Борцов революции».