Westlich der Stadt gelegenes, ehemaliges Nebenkloster der Abtei Fulda, um 1020 als "monasterium novum“ in der Folge der Reform von Gorze gegründet. Unter dem von Kaiser Heinrich II. eingesetzten Abt Richard aus Amorbach wurden Klausur und Kirche errichtet, letztere wurde 1023 vom Mainzer Erzbischof Aribo dem hl. Andreas geweiht. Mit dem Bau dieses Klosters war das Viereck der um das Hauptkloster gelagerten Propsteien Frauenberg, Johannesberg und Petersberg geschlossen (in der im 11.Jh. abgefaßten Vita des hl. Erzbischofs Bardo von Mainz als lateinisches Kreuz interpretiert). Die Andreasberger Propstei entwickelte sich zur bedeutendsten unter den Vieren, hatte die meisten Besitzungen und die höchsten Einkünfte, und diente deshalb seit der Mitte des 16.Jhs. zur Versorgung des Stiftsdechanten, der dann auch die Propstei übernahm. 1715 wurde die Klosterkirche Pfarrkirche des Ortes Neuenberg, mit der Säkularisation 1803 wurde sie Filialkirche der Dompfarrei, die anderen Gebäude wurden als Staatsdomäne umgenutzt. Erst 1929 ging die Propstei wieder in Besitz des Bistums über, die Kirche ist heute erneut Pfarrkirche von Neuenberg.
Die bestehende, barock überformte Anlage der Kirche entspricht in ihrem Grundriß und ihrer Bausubstanz noch weitgehend dem Gründungsbau des frühen 11.Jhs., der aus einem einschiffigen Langhaus von fast 45 m Länge und einem weit ausladenden, östlichen Querhaus bestand. Unmittelbar am Querschiff befand sich eine halbkreisförmige Apsis mit einer nach Westen vorstoßenden Krypta. Im Anschluß an das Langhaus war vermutlich noch eine niedrige Westvorhalle angebunden. Von dieser Anlage blieb die gesamte Ostpartie mit Querhaus in voller Höhe erhalten, lediglich das Langhaus büßte bei späteren Umbauten den oberen Teil der Längswände sowie wahrscheinlich die gesamte Westwand ein. Abgesehen von der Krypta beschränkte sich die ursprüngliche Ausstattung in Entsprechung zu dem strengen architektonischen Gerüst auf einen grauen, schmucklosen Estrichboden und weiß gekalkten Innenwänden mit geringen ornamentalen Malereien.
Im 12.Jh. erhielt die Kirche den bestehenden dreigeschossigen Westturm mit Schallarkaden und einem spitzen Helm. Die Johanneskapelle im ersten Turmgeschoß richtete Propst Gerlach 1480 ein. Aus der Zeit um 1500 sind Nachrichten über die Erneuerung von Klausurgebäuden bekannt. Erste Renovierungsmaßnahmen erfolgten unmittelbar nach den Zerstörungen des Dreißigjährigen Krieges hauptsächlich im Chorbereich. Vermutlich verlängerte man nun auch - spätestens bis zum Jahr 1647 - das Kirchenschiff bis zum Turm. Zwischen 1766 und 1768 kam es unter Propst Karl von Fechenbach zu einer tiefgreifenden Modernisierung des ottonischen Baues, wobei u.a. die obere Zone der Langhauswände abgetragen wurde, um größere Fensteröffnungen zu schaffen und ein Holzgewölbe einziehen zu können, das dann stukkiert wurde. Die Wände gliederte man durch flache Pilaster. Als Abschluß dieser Baumaßnahmen wurde dem Turm die geschweifte Zwiebelhaube aufgesetzt.
Die heutige Ausstattung der Propsteikirche stammt zum großen Teil aus der Zeit dieses Umbaues, so die Kanzel des Hofschreiners Karl Philipp Arnd an der südlichen Langhauswand, die Beichtstühle, ein Teil des Kirchengestühls sowie Orgelempore und -prospekt. Der Hochaltar mit dem Retabel des Fuldischen Hofmalers Hans Klemp datiert von 1647 und befindet sich, nachdem er zwischenzeitlich seinen Standort in Seiferts/Rhön hatte, seit 1985 wieder an seinem ursprünglichen Ort. Die 1669 entstandenen Seitenaltäre stehen seit 1952 in der Pfarrkirche zu Rasdorf.
Folgende weitere Inventarstücke wurden nicht für ihren derzeitigen Standort geschaffen: die geschnitzten Figuren einer spätgotischen Pietà aus Körnbach bei Hünfeld und einer Muttergottes (1. Hälfte 18.Jh.); außerdem ein großformatiges Ölgemälde mit der Verkündigung an Maria, vermutlich aus der Werkstatt des Fuldaer Hofmalers Alexander Wiskemann (gestorben 1622), und ein kleineres Ölbild mit einer Kreuzigungsszene von Johann Andreas Herrlein (2. Hälfte 18.Jh.).
Die am nördlichen Querhausarm angebaute Sakristei beherbergt eine spätgotische Sakramentsnische mit dem Lamm Gottes als Relief im Dreiecksgiebel.
Ungewöhnlich groß ist die Zahl der Grabdenkmäler in der Kirche. Neben dem kulturhistorisch bedeutenden, nur in Resten erkennbaren Grab des Gründerabtes Richard, das im Chorbereich vor dem Hochaltar lag und durch einen heute freiliegenden "oculus“ mit der Krypta verbunden war, sind weitere bis ins 11.Jh. zurückreichende Grabplatten sowie fast alle Epitaphien der Neuenberger Pröpste des 18.Jhs. erhalten.
Von besonderer Bedeutung ist die über zwei Treppen zugängliche Hallenkrypta. Sie besitzt eine komplizierte Gewölbekonstruktion aus gurtlosen, sich durchdringenden Tonnengewölben, die von vier Säulen mit Würfelkapitellen getragen werden. Auf den Gewölben und in den Nischen der drei Fenster befindet sich eine 1932 entdeckte Ausmalung, die wohl aus der Erbauungszeit stammt und zwischen Ornamentbändern Figürliches zeigt: Christus in der Mandorla, Szenen aus dem alten und neuen Testament, Könige und Heilige in Medaillons, ein Engelfries. Die alten, seitlich der Treppe sichtbaren Chorschranken tragen außerdem noch eine Malerei aus der ersten Hälfte des 13.Jhs., wohl als thronende Apostel zu interpretieren.
Von den ehemaligen Klausur- bzw. Propsteigebäuden sind nur noch östlicher und nördlicher Flügel als Wiederaufbau nach Brand vorhanden. Der Grundriß des Westflügels ist in erneuerten Mauerfragmenten heute wieder ablesbar. Die einfachen, mit Satteldächern versehenen Baukörper stammen in ihrem Kern wohl noch aus dem späten Mittelalter, der Kreuzgang mit seinen Rundbogenfenstern ist vermutlich um 1600 entstanden. Eine kleine, kreuzgratgewölbte Kapelle befindet sich im Ostflügel.
Auf dem Propsteigelände, das von einer weitgehend intakten Mauer umgeben ist, steht östlich der Kirche noch ein großer, zweiflügeliger Wirtschaftstrakt. Der ehemalige Friedhof und der Propsteigarten liegen westlich. Das Friedhofskreuz mit Korpus stammt von 1837. Am Verbindungsweg von der Neuenberger Straße zur Kirche steht seitlich noch ein schöner Bildstock von 1737. Der mit einem Doppelkreuz bestückte Aufsatz zeigt jeweils als Relief auf der einen Seite das Kruzifix, auf der anderen den Apostel Andreas.
Die ehemalige Propstei Neuenberg ist ein wichtiger Beleg für die wirtschaftsgeschichtliche Entwicklung der Benediktinerabtei Fulda. Die Propsteikirche ist darüber hinaus ein Kulturdenkmal von besonderem Rang, weil sie zum einen in ihrer auch architektonisch interessant gestalteten Krypta seltene, gut erhaltene Wandmalereien der Romanik enthält, zum andern mit ihrer reduzierten Architektur Zeugnis einer monastischen Reformbewegung ist, die von großer kirchengeschichtlicher Bedeutung war.