Il desiderio dei russi di recarsi a Bari, per inchinarsi davanti alle reliquie di San Nicola taumaturgo, è stato sempre grande е ciò si spiega con l'eccezionale venerazione diffusa in Russia per il santo di Mira di Licia. Com'è noto, le reliquie di San Nicola sono state portate da Bisanzio in Occidente nel 1087, quando Bari era sotto il potere dei Normanni e sotto il pastorale del Papa (per le reliquie è in seguito costruita la grandiosa basilica in cui tuttora si trovano).
Alcuni pellegrini russi del XIX e inizio del XX secolo hanno lasciato interessanti relazioni su Bari, ricche di impressioni sulle difficoltà del viaggio, ma anche sulla "realtà cattolica" di San Nicola; a molti non piaceva infatti la raffigurazione del santo con i paramenti da vescovo latino, "gli indecenti girotondi degli italiani" presso la basilica, il rito locale di venerazione delle reliquie, "lo sfacciato sfruttamento e il ladrocinio insolente" dei baresi. I pellegrini russi erano soprattutto rattristati dalla mancanza di liturgie ortodosse a Bari.
L'idea di costruire la chiesa russa di Bari risale al 12 maggio 1911, quando viene istituito il comitato di Bari con a capo il principe A. A. Širinskij-Šichmatov, esperto di arte russa antica, sotto l'alto patrocinio dell'imperatore Nicola II, che vi contribuisce con diecimila rubli. Compito del comitato è l'edificazione di una foresteria italiana comprendente un ospizio per i pellegrini russi e una chiesa che rappresenti degnamente l'arte ortodossa.
Nella primavera del 1911 giungono a Bari il principe
N. D. evachov e il famoso architetto V. A. Pokrovskij, che fa una ricognizione del terreno acquistato per la chiesa e dà la propria approvazione al luogo della prevista costruzione: 12 mila metri quadrati in via Carbonara, odierno сorso Benedetto Croce, 130. Probabilmente Pokrovskij era uno dei candidati per l'incarico al progetto della foresteria, che è invece ottenuto da A. V. Ščusev con l'appoggio, verosimilmente, della principessa Elizaveta Fёdorovna, per la quale l'architetto aveva costruito il convento di Marta e Maria vicino a Mosca. Nell'archivio personale di Ščusev si è conservato un gran numero di schizzi, di varianti di progettazione degli interni, di disegni esecutivi della foresteria, datati 1912-1914.
La chiesa russa di Bari, edificata contemporaneamente alla chiesa russa "di Bari" a Pietroburgo e a questa molto simile, è a pianta quadrata con i tetti a due spioventi, una sola cupola a forma di elmo e i campanili sulla parete occidentale. ‘Ideologo' dei due edifici, che riprendono lo stile ispirato dell'architettura di Pskov e Novgorod, è il principe Širinskij-Šichmatov, che raccoglie di persona anche le antiche icone per le iconostasi di ambedue le chiese (a Bari non furono mai inviate a causa dello scoppio della guerra). Il principe accarezzava l'idea di allestire a Bari, nei locali della foresteria, un museo dell'arte russa antica, che sarebbe stato il primo al di fuori dei confini della Russia e aveva previsto una esposizione di icone antiche, di edizioni rare e di fotografie di tutte le chiese dedicate a San Nicola in Russia (progetto da affidare a K. S. Petrov-Vodkin). Oltre alla chiesa, che poteva contenere 200 fedeli, il progetto della foresteria comprendeva una casa del pellegrino con tre camere al primo piano e quattordici al secondo, refettorio, toilettes, un reparto per i pellegrini malati, lavanderia, bagno.
Nel marzo 1913 viene inviata in missione a Bari una commissione ispettiva per seguire i lavori di costruzione, della quale entrarono a far parte il rettore della erigenda chiesa, padre Nikolaj Fedotov, l'architetto I. D. Nikol'skij in qualità di soprintendente ai lavori, il salmista K. N. Faminskij e il capocantiere I. D. Nikol'skij. Le autorità civili di Bari plaudono l'iniziativa russa: il 22 maggio (giorno della traslazione delle reliquie) 1913, quando viene solennemente posta la prima pietra della foresteria, il primo cittadino di Bari e il presidente della regione Puglia giungono al cantiere, su cui sventolavano le bandiere russa e italiana. Il clero cattolico non prende parte alla cerimonia della posa della prima pietra. Nelle fondamenta della chiesa sono collocate lettere in russo e in italiano e alcuni rubli d'argento. Nell'area viene rapidamente edificato un edificio provvisorio con un campanile e un locale al piano superiore per la chiesa temporanea, che è consacrata già il 24 dicembre 1913. Alla cerimonia di consacrazione padre Nikolaj Fedotov proclama l'inizio della rinascita dell'ortodossia in Puglia.
La guerra, la rivoluzione del 1917 e la successiva emigrazione interrompe il flusso dei pellegrini. Una serie di controversie giuridiche consegnano al municipio di Bari il possesso delle strutture della foresteria e della chiesa che viene consacrata il 22 maggio 1955.
Negli ultimi tempi l'interesse per la chiesa di Bari si è riacceso: il governo russo ha espresso l'intenzione di rientrare in possesso delle proprietà estere. Nel 2007 l'edificio è stato riconsegnato alla Russia.
