Предыстория римско-католического костела начинается в 60-е годы XIX века. После подавления польского восстания 1863 г. проводилась массовая высылка повстанцев в различные губернии России, тысячи католиков-поляков оказались в Тамбовском крае. Многие со временем прижились в Тамбове, но возникла потребность в храме как духовно-культурном центре. И в октябре 1896 года тамбовские католики в зале Публичной библиотеки приняли решение о строительстве в Тамбове собственного храма. Шестьдесят три представителя, среди которых были Свирчевские, Каменские, Вольские, Кучевские и многие другие, обсудили вопросы о средствах и месте строительства костела; сразу же была открыта подписка для сбора средств. Для возведения костела предлагалась усадьба М. А. Кучевского на Покровской улице, рядом с домом А. Н. Чичерина. Усадьба была довольно большой: 13 саженей в ширину и 37 саженей в длину. На ней предполагалось построить временный молитвенный дом, который можно было бы использовать как богадельню после строительства каменной церкви. Для устройства богадельни предназначался капитал, завещанный врачом Вороничем. Проект и смета были разработаны в 1898 г. Вопросами строительства занимался совет, в который входили четыре представителя – К. К. Вольский, инженер-строитель Теофил Свирчевский, судебный следователь А. Костецкий и инженер-технолог Казимир Дембовский. Строительные работы осуществлялись Теофилом Свирчевским. Огромное здание костела было построено в предельно короткие сроки: 25 мая 1903 года в костеле уже совершалось богослужение, несмотря на то, что в храме недоставало образов и хоругвей и были временные алтари. Внутренняя отделка и устройство иконостасов продолжались в течение нескольких последующих лет.
Готический стиль собора – вытянутого по продольной оси здания с многочисленными стрельчатымиарками, карнизами, изящной орнаментацией и двумя высокими островерхими башнями был уникальным не только для Тамбова, но и для всей центральной России. Русский искусствовед Г. К. Лукомский (1884 – 1945) увидел в нем отзвуки влияния русского искусства. Однако в подлинном виде этот памятник провинциальной художественной архитектуры России сохранился только на редких дореволюционных открытках. При костеле, который народ назвал польским, был учрежден приход и назначен католический священник, подчинявшийся Могилевскому митрополиту. Усадьба вокруг костела была наполнена зеленью и розовыми цветниками; здание обрамляли величественные ели. Только тридцать два года служил костел верующим. В 1918 году городские власти сделали первые попытки реквизировать имущество костела и изъять метрические книги. Обеспокоенный Могилевский митрополит, обращаясь к тамбовскому губсовдепу, писал, что приходское имущество католических костелов в России образовано из добровольных пожертвований граждан других государств и национальностей, что русский народ и государство не внесли ничего в это имущество и поэтому не имеют на него никаких прав. В начале 20-х годов была закрыта библиотека при костеле, а книги вывезли в Польский партийный клуб. Ксендз католического прихода Казимир Вержбицкий был репрессирован в 30-е г. XX века.Органная музыка умерла в польском костеле в феврале 1935 года. В это время, как сообщали официальные источники, община верующих распалась и костел для богослужений не использовался.Горсовет предлагал желающим взять помещение в аренду «в культурных целях”. Но богатых организаций в городе не нашлось, костел был закрыт; с этого времени началось разрушение здания и разграбление его имущества. В июне 1936 года горсовет предложил переоборудовать костел под швейную мастерскую, а имущество ликвидировать в соответствии с постановлением ВЦИК и СНК от 8 апреля 1929 года. Духовные ценности Римско-католического костела были растрачены, а через несколько лет после Великой Отечественной войны был демонтирован орган. Собрать его на новом месте не удалось. Длительное время здание костела использовалось Тамбовским ремонтно-подшипниковым заводом.К середине 90-х годов XX века тамбовский костел представлял собой печальное зрелище:разрушенные звонницы, изуродованный фасад, изъеденные кислотными парами стены, затопленный подвал. Но в это время усилиями журналиста К.Н. Денисова в Тамбове возродилась католическая община, зарегистрированная в 1996 г. как Римско-католическое объединение Воздвижения Святого Креста. В том же году здание костела возвратили верующим. Благодаря собранным в Польше средствам удалось начать восстановление храма, постепенно приобретающего первозданный вид. Уже в 1998 г. мэром Тамбова А.Ю. Ильиным был зажжен Вечный Свет в храме. В августе 2000 года были освящены кресты и воздвигнуты шпили над колокольнями. Освящение и установка колоколов состоялись 2 октября 2001 года. Три колокола общим весом 1000 кг были подарены тамбовскому римско-католическому приходу польской фирмой «Производство и ремонт колоколов Яна Фельчинского». Возрождение костела под руководством настоятеля прихода отца Йозефа Матиса в основном завершилось.В ноябре 2007 года около храма установили памятник святителю Николаю (скульптор — Зураб Церетели).