הכנסייה נבנתה בשנת 675 ככנסיית מנזר בארקינג (Barking Abbey) הסקסוני, על יסודות מבנה רומי, וכונתה "כל ה"קדושים" בארקינג" (All Hallows Barking). שרידי המבנה הרומי נמצאים בקריפטה של הכנסייה.
הכנסייה הורחבה ושופצה מספר פעמים בין המאות ה-11 וה-15. בשל קרבתה למצודת לונדון שימשה הכנסייה בפועל ככנסייה של בית המלוכה ובתקופת אדוארד הרביעי קיבלה מעמד זה באופן רשמי, וכל המוצאים להורג במצודת לונדון נקברו בכנסייה.
הכנסייה נפגעה בהתפוצצות בשנת 1649 והמגדל המערבי שלה נהרס. מהשרפה הגדולה של לונדון בשנת 1666 ניצלה הכנסייה בזכות האדמירל ויליאם פן, אביו של ויליאם פן מייסד פנסילבניה, שהרס את כל הבתים סביבה כדי להרחיק ממנה את הלהבות.
הכנסייה שופצה בסוף המאה ה-19, ובשנת 1926 נערכה חפירה ארכאולוגית בקריפטה של הכנסייה, אז נתגלו מרצפות של רחוב רומאי וכן חפצים רבים מהתקופה הרומית.
במהלך הבליץ במלחמת העולם השנייה נהרסה הכנסייה כמעט לחלוטין. בשנת 1957 נחנכה הכנסייה לאחר שנבנתה מחדש תוך שימוש בלבנים ובקטעי הקירות ששרדו.
מקור הקירות החיצוניים של הכנסייה במאה ה-15, ואחת מדלתות הכניסה היא מהמאה ה-7. כמו כן יש בכנסייה פסלים של "קדושים" נוצרים מהמאות ה-15 וה-16 ששרדו את ההפצצות ואגן טבילה מעשה ידי גרינלינג גיבונס משנת 1682.
.svg){kind=spacer}
אתר האינטרנט הרשמי של כנסיית כל ה"קדושים" שליד המצודה