Петропавловский собор построен на возвышенном склоне горы, спускающемся к пойме р. Ушайки. Эта возвышенность ещё с XVII века известна как «Мухин бугор» – по имени раскаявшегося разбойника Мухи, бывшего грозой окрестных лесов на рубеже XVII–XVIII веков. До постройки храма на этом месте долгое время стоял деревянный поклонный крест и часовня.
Храм построен в начале XX века по проекту архитектора А. И. Лангера в неорусском стиле. Главный престол в честь святых апостолов Петра и Павла был освящён в 1911 году. Южный (во имя святого Иоанна Предтечи) придел – в 1913 году, северный (в честь Рождества Пресвятой Богородицы) придел – в 1915 году. Службы прекращены с 1938 году, а в 1940 году здесь размещались склады спиртзавода. Богослужения возобновились в 1945 году. В период 50–90-х гг. XX века Петропавловский собор и Свято -Троицкий храм были единственными действующими православными церквями Томска.
Особенностью самого здания храма является его декор и деталировка, выполненные из красного лицевого кирпича и жёлтого песчаника. Фасад здания украшен терракотовой плиткой.
В настоящее время при Петропавловском соборе действуют воскресная школа, молодёжный клуб и библиотека.
Главными святынями храма являются крест-мощевик с частицами мощей 24 святых, и землёй из Ефеса от гроба апостола и евангелиста Иоанна Богослова.
В собрании икон церкви – икона Святых апостолов Петра и Павла с частицами их мощей, икона Знамения Божией Матери работы томских иконописцев И. Панкрышева и С. Вепрева. Специально к освящению собора из Афона в Томск были доставлены четыре иконы на кипарисовых досках: «Введение во храм Пресвятой Богородицы», «Рождество Христово», «Усекновение Главы Иоанна Предтечи», «Покров Пресвятой Богородицы». Иконы были выполнены Афонскими монахами-иконописцами.
Чудотворной иконой является образ Святого Николая Мирликийского, который уцелел после ночного пожара во время Крещенских праздников в 1986 году. Пожар угас сам собой, дойдя до иконы без человеческого вмешательства. Следы пожара можно увидеть и сегодня на обугленной раме иконы.