Початкова Троїцька церква існувала у Верхньому місті вже з XVII століття. Вона стояла на місці нинішнього скверу, що перед готелем Hyatt Regency Kyiv, поруч із вулицею Алли Тарасової.
Проте з початком розбудови Верхнього міста у середині XIX століття, у 1854-1857 роках, на Софійській площі була споруджена будівля Присутственних місць. Також почалося заселення Нової Забудови у Либідській частині Києва.
Митрополит Філарет започаткував перенесення дерев'яної Троїцької церкви з Верхнього міста до Нової Забудови для упорядкування парафій та будівництва храмів у нових районах Києва.
Проєкт храму був розроблений архітектором Павлом Спарро у 1852 році, і вже в 1854 році його затвердив імператор. Зведення нової церкви розпочалося у 1856 році та залучало значну участь священика Євфимія Ботвиновського, церковного старости Миколи Балабухи та інших благодійників.
Початково планувалося використати деревину з розібраної у 1858 році старої Троїцької церкви для будівництва нового храму, але виявилося, що ці будівельні матеріали не підходять для повторного використання. Тому зі старої церкви перенесли лише реліквії та церковне приналежності до нової споруди.
Дерев'яна церква
Нову Троїцьку церкву освятили 12 жовтня 1858 року. Це була дерев'яна церква на мурованому фундаменті з дерев'яною шатровою дзвіницею. У 1865 році або у 1880-х роках будівлю обклали цеглою.
Навколо церкви була простора садибна ділянка, на якій пізніше збудували кам'яний будинок для священників, малий кам'яний будиночок для сторожа та дерев'яний сарай.
Дерев'яна Троїцька церква мала російські архітектурні форми, з хрещатим планом, шатровим завершенням бані та дзвіниці. Фасади церкви були прикрашені стриманим цегляним декором, таким як карнизові кронштейни, сандрики та пілястри.
У середині церкви знаходився бароковий дерев'яний іконостас, виготовлений у 1760 році за проєктом архітектора Івана Мічуріна. Зі старої Троїцької церкви перенесли сюди реліквії та церковне приналежності, зокрема, ікону Божої Матері.
В церкві були освячені два вівтарі - на честь Пресвятої Трійці та великомученика Пантелеймона, добудованого у 1880-х роках. Навколо церкви був зведений цегляний мур із сторожкою.
Будівництво мурованої церкви
На початку XX століття район Нової Забудови в Києві значно розширився, і став необхідний більший, кам'яний храм. У 1901 році, поруч з Троїцьким храмом, римо-католицька громада збудувала величний костел святого Миколая.
У тому ж 1901 році, був створений комітет для будівництва нової мурованої Троїцької церкви, яка повинна була не поступатися розмірам католицькому костелу.
Проєкт нової церкви був підготовлений архітектором Євгеном Єрмаковим у 1902 році. За цим проєктом, нова Троїцька церква повинна була бути великою двоповерховою спорудою з п'ятьма цибулястими банями - великою центральною на масивному барабані та чотирма меншими по кутах, з пишним декором фасадів, що поєднує в собі елементи псевдоросійського стилю та одного з різновидів модерну - неоросійського стилю.
Також, до церкви повинна була прилучатися висока п'ятиярусна дзвіниця із видовженим шатром, увінчаним цибулястою банькою. Планувалося, що храм буде вміщати до 3000 осіб, а його висота буде складати близько 56,5 м, дзвіниці - понад 65 м, тобто будівля мала конкурувати за розмірами з 60-метровим Миколаївським костелом.
Будівництво розпочалося у вересні 1911 року, проте через Першу світову війну й радянський період будівництво зупинилося, і згодом недобудовану церкву розібрали у 1930-х роках.
Відродження храму
У 2011 році Київрада прийняла рішення передати ділянку зруйнованої Троїцької церкви, розташованої на розі вулиць Шота Руставелі і Жилянської, на користь громади Української Православної церкви.
25 вересня 2011 року відбулася перша божественна літургія на місці зруйнованого храму. Молебень очолив професор протоієрей Віталій Косовський з благословення митрополита Київського і всієї України Володимира.
Починаючи з 13 червня 2015 року, розпочалися будівельні роботи з відтворення храму за проєктом архітектора Ольги Кругляк, пізніше проєкт був скоригований архітектором Олегом Калиновським та інженером Іваном Деченком.
25 червня 2021 року Митрополит Київський і всієї України Онуфрій освятив хрести, які потім були встановлені на головну та бічні бані храму.
Парафію Троїцької церкви очолює протоієрей Костянтин Курбанов, а при церкві діє культурно-просвітницький центр та недільна школа для дітей і дорослих.
Новий храм буде в стилі московського узорччя, що викликає негативний відгук в суспільстві.