En 1840, los cónsules de Estados Unidos, Suecia e Inglaterra, solicitaron al gobierno uruguayo autorización para levantar un templo protestante alegando la inexistencia de un espacio dedicado exclusivamente a este culto. Esta iniciativa recién prosperó tres años más tarde, cuando Samuel Lafone obtuvo la licencia para la construcción de dicha iglesia, cuya piedra fundamental fue colocada el 1º de enero de 1844 por el Comodoro Purvis, el Comandante en Jefe de las Fuerzas Navales de Su Majestad Británica en Montevideo. Una vez iniciadas las obras, Lafone donó el templo al gobierno británico. El edificio primitivo de la Iglesia de la Santísima Trinidad -primero en Uruguay y en la América hispana-, construido por el arquitecto Antonio Paulliere e inaugurado en 1845, estaba ubicado en las inmediaciones del Cubo del Sur, sobre la calle Santa Teresa.
Emplazado en uno de los predios destinados a desaparecer a causa de la construcción de la Rambla Sur, en el mes de agosto de 1934, una vez que el gobierno municipal adquirió la propiedad del edificio, se iniciaron los trabajos de demolición de templo. La Comisión Financiera de la Rambla Sur, con el beneplácito del gobierno comunal, además del pago de la indemnización por el edificio y su predio, otorgó un terreno situado enfrente del expropiado, en el área comprendida entre las calles Reconquista, Brecha y Treinta y Tres, comprometiéndose a convertir la superficie no edificada en jardines. El desafío era construir un templo de cara al mar que fuese una réplica del original.
Por consiguiente, antes de dar comienzo a la demolición, la Comisión permitió retirar piezas de valor -vitreaux, placas conmemorativas, moblaje del altar y el pupitre, etc.- con el objetivo de que fuesen reutilizadas en el nuevo edificio.
El nuevo templo, inaugurado el 6 de junio de 1936, respetaba en gran medida los lineamientos arquitectónicos de su antecesor. Entre las variaciones, se destaca fundamentalmente la desaparición por motivos estéticos de las dos torres que se levantaban en la parte posterior.
Durante el lapso comprendido entre la demolición del viejo templo y la construcción del nuevo, los servicios religiosos de la Iglesia Anglicana se realizaron en el edificio que anteriormente había servido de sede al Banco Británico de la América del Sud, ubicado en las calles Zabala y 25 de Mayo.