Im Jahre 1047 wurde Balje das erste Mal urkundlich erwähnt. Etwa um diese Zeit wurde auch eine erste Kapelle in Balje errichtet. Anfang des 14. Jahrhunderts wurde dann eine große Kirche gebaut, die der Jungfrau Maria geweiht wurde. Es war eine große, prächtige Kirche, die auf einer Wurt gebaut wurde und der Vorgängerbau der jetzigen Kirche war. Um 1540 wurde in Balje die Reformation eingeführt.
Am 2. Weihnachtstag 1936 ereignete sich ein verheerendes Unglück: Eine Kerze war nach dem Gottesdienst nicht gelöscht worden und setzte die Kirche in Brand. Als man das Feuer bemerkte, war der Schaden zu weit fortgeschritten, um die alte Kirche zu retten. Nachdem die alte Kirche niedergebrannt war, wurde an derselben Stelle eine neue Kirche errichtet. Die Grundsteinlegung erfolgte 1937 und am 03. April 1938 konnte die neue Kirche geweiht werden. Der Name – St. Marien Kirche – blieb erhalten. Außerdem konnten ein paar wenige Dinge beim Brand aus der alten Kirche gerettet werden, unter anderem kann man bei genauem Hinsehen einige alte Steine und Balken in der heutigen Kirche wiederfinden.
Die neue Kirche ist nur etwa halb so groß wie die alte Kirche und auch in ihrer Ausstattung deutlich bescheidener. 1984 wurde die Kirche – unter großer Eigenleistung der Gemeindeglieder – renoviert. Eine große Neuerung war auch der Einbau einer neuen Orgel 1999, durch die Orgelwerkstatt Harseborg in Ostfriesland. Es bedurfte großer Anstrengungen für eine kleine Gemeinde, hier die nötigen Spendengelder aufzubringen.