С возведением в 1861 году станицы Коряковской в заштатный город Павлодар, казачье поселение по-прежнему оставалось на особом положении, имея независимое от гражданских властей военно-административное устройство. Поэтому Павлодар был разделен на две части – станичную и городскую (или мещанскую), где стали селиться разночинцы, не принадлежавшие к казачьему сословию.
Флоро-Лаврская церковь, находившаяся в станичной части города, считалась казачьей, но прихожанами церкви были также и городские жители, поскольку своей церкви не имели.
Проектный план развития города, составленный в 1862 году, предусматривал строительство в мещанской части города нового храма.
2 июня 1890 года павлодарский мещанин Дмитрий Николаевич Асямов и священник Флоро-Лаврской церкви Алексий Гусев отправили Степному генерал-губернатору барону М. А. Таубе телеграмму, в которой ходатайствовали о разрешении архитектору Семипалатинской области принять наблюдение за постройкой новой церкви в Павлодаре. Как сообщалось в телеграмме, подрядчик, рабочие, материалы готовы, но закладка задерживалась прибытием архитектора, и подрядчик терпел убытки. В этот же день барон Таубе сообщил об этом военному губернатору Семипалатинской области.
Решение о строительстве новой церкви было принято и в 1893 году, тщанием городских жителей и при поддержке купца 1-й гильдии Артемия Ивановича Дерова и мещанина Дмитрия Николаевича Асямова Троицкая церковь была построена. Ее еще стали называть «мещанской» или «белой» – по цвету стен.
Возведенный каменный однопрестольный храм был квадратный в плане, пятиглавый, с большими окнами и полукруглой алтарной апсидой, наверху которой – маленькая луковичная главка. В одной связи с храмом – двухъярусная колокольня (восьмерик на четверике), завершенная главой-луковицей. Между храмом и колокольней – трапезная с выступающими приделами, увенчанными главками. Вход в храм увенчан шатром с главкой.
Храм стал украшением города, однако, по отзывам причта, был малопоместительным и требовал расширения. Вопрос расширения был поставлен в начале 1904 года, но окончательное его решение отложили до более подробного осмотра здания епископом Омским и Семипалатинским Михаилом при следующем посещении Павлодара в июле 1904 года.
В этом же году Строительным Отделением Семипалатинской области был утвержден проект пристройки к Свято-Троицкому собору, но отсутствие необходимых средств затянуло начало строительных работ.
В 30-е годы собор перешел в руки обновленцев. На заседании президиума павлодарского горсовета 17 декабря 1932 года обсуждался вопрос о передаче Свято-Троицкого собора в ведение Горкомхоза. В связи с тем, что община не имела средств отапливать собор и фактически им не пользовалась, а также по причине неуплаты церковной общиной в течение нескольких лет налогов по земренте и со строений, 10 марта 1935 года на заседании Павлодарского горисполкома было решено передать пустующий храм в аренду. Было предложено передать собор Дому обороны и предложить использовать под клуб физкультуры и проведение военных занятий молодежи. 30 июня 1935 года на общем собрании членов обновленческой общины было признано невозможным дальнейшее самостоятельное существование общины и решено оставить занимаемое здание Свято-Троицкого собора. 4 июля 1935 года на заседании президиума Павлодарского горисполкома было принято постановление: «Ввиду того, что община Павлодарского собора своим решением отказалась от занимаемого помещения (церкви), а также и ценностей, находящихся в ведении данной общины, а поэтому обязать зав[едующего] горкомхозом т. Проненко немедленно принять помещение (церковь Троицкого собора), а также и все находящиеся ценности. Снять с Троицкого собора колокола и поручить горФО сдать [в] госфонд в соответствующие организации».
В феврале 1936 года председатель Павлодарского горсовета Н. Н. Горбенко в письме председателю Восточно-Казахстанского облисполкома, сообщал: «…мы же задыхаемся в помещениях, а помещение Троицкого собора уже год как не используется. Павлодарские власти намечали открыть там спортивный клуб. «Еще раз прошу не задержать наши материалы, разрешить нам открыть в ней культурный очаг».
Президиум Павлодарского горсовета 23 марта 1937 года принял постановление о разборе здания Свято-Троицкого собора на кирпич для строительства школы.
Комиссия Павлодарского горсовета, осмотрев здание Свято-Троицкого собора 15 апреля 1937 года, пришла к выводу, что здание собора непригодно для использования под школы, культурно-бытовые помещения и жилье.
После освобождения обновленцами здание Троицкого собора было принято в ведение Горкомхоза и спустя два года разобрано на кирпич, который был использован для строительства рядом с уничтоженным собором 16-квартирного жилого дома.
