Le nom de l'église soulève aujourd'hui des questions, car ce que nous appelons le champ de Khodynka est situé à un autre endroit, à l'intérieur du chemin de fer périphérique et à deux kilomètres de l'église. Cependant, au XIXe siècle, le champ de Khodynka occupait une superficie beaucoup plus grande et s'étendait presque jusqu'à Shchukino. Dans les années 1900, le chemin de fer périphérique l'a divisé en deux parties. Dans la première moitié du XIXe siècle, des camps militaires ont commencé à apparaître à Khodynka, situés dans la partie est du champ, plus près de Shchukino. Au début du XXe siècle, cette partie était appelée le Champ militaire, et depuis 1922, le Champ d'Octobre. Dans les années 1930, des baraquements ont commencé à y être construits, et plus tard, dans les années 1940-50, des maisons stalinniennes ont vu le jour. Les camps militaires se trouvaient au nord de l'actuelle rue Maréchal Rybalko. Au nord d'eux se trouvait le Grand bosquet de Tous les Saints, dont il ne reste aujourd'hui qu'une petite partie.

L'église a été construite sur le territoire des camps militaires, près de l'hôpital militaire de Moscou, et les principaux paroissiens étaient des cadets et des officiers. La première église, dédiée à saint Pantaléon, était en bois et a été érigée en 1897. Son architecte était I. Molchanov. L'église actuelle a été construite à côté de la structure en bois en 1902 et a été dédiée à l'icône «Skoroposlushnitsa», à laquelle on faisait appel en cas de détresse et de situations d'urgence, telles que des naufrages, des incendies et des inondations.

L'église a été posée le 8 juin 1901, et elle a été consacrée le 1er août 1902. Malheureusement, l'architecte est inconnu. Le journal «Nouvelles ecclésiastiques de Moscou» a rapporté que lors du service religieux, dirigé par le protopresbytre de l'armée et de la marine A. Zhelobovsky, étaient présents le Grand-Duc Serge Alexandrovitch et la Grande-Duchesse Élisabeth Fiodorovna. Serge Alexandrovitch était alors gouverneur général de Moscou.

L'église est réalisée dans le style néo-russe, stylisée selon le décor russe du XVIIe siècle. Cela concerne des détails tels que le portail en arc du côté sud-ouest. Il existe plusieurs prototypes de ce portail à Moscou, par exemple, dans les églises de Cosme et Damien à Starye Panek, de la Trinité à Listy et d'autres. Les fenêtres avec des sommets en forme de kil sont également caractéristiques du décor pré-péterien. Cependant, une cloche de ce type au XVIIe siècle était construite séparément de l'église. Les «larges» verticales sur les bords de la façade et les rangées de niches carrées avec des losanges au centre sont également empruntées au décor, mais au XVIIe siècle, de tels éléments étaient utilisés pour décorer les galeries de contournement.

La partie principale de l'église est un carré avec une coupole unique. Sous le corniche se trouve une frise de kokoshniks, qui sont trop petits par rapport aux prototypes du XVIIe siècle, ce qui renvoie aux frises à arcatures du XVe siècle, par exemple, à l'église de la Transfiguration dans le Kremlin.

Après la révolution, l'église en bois a été démolie, et l'église en briques a été fermée, décapitée et la partie supérieure du clocher a été détruite. À l'intérieur, des entrepôts ont été aménagés, le dernier d'entre eux, dans les années 1980, appartenant à l'entreprise «Soiuzsamotsvety». L'église a été à nouveau consacrée en 1992 et restaurée. Cependant, lors de la restauration, l'apparence originale du bâtiment a été modifiée : les murs en briques rouges ont été enduits.