Aicha vorm Wald ist eine der ältesten Pfarreien im Bistum Passau und war früher auch Dekanatssitz. Die Pfarrei wurde schon im 8. oder 9. Jahrhundert errichtet.
Bayernherzog Odilo (737-748) überließ Aicha den Bischöfen von Passau als Schenkung. Diese vergaben Aicha als Lehen an Adelige, bis Bischof Konrad 1055 Aicha dem Domkapitel schenkte. Am 20.04.1179 bestätigte Papst Alexander III diese Schenkung. 1120 wird die Pfarrei erstmals urkundlich erwähnt. Die Urpfarrei Aicha hatte die Größe eines kleinen Fürstentums. Die heutigen Pfarreien Eging, Thannberg, Thurmansbang, Zenting, ein Teil von Innernzell, und Schönberg, Tittling, Neukirchen vorm Wald und Fürstenstein unterstanden den Pfarrherren von Aicha. Sechs berittene Kooperatoren unterstützten den Pfarrer in der Seelsorge.
Anstelle der Holzkirche aus dem 10. Jahrhundert wurde im Mittelalter eine steinerne gotische Kirche errichtet, die der Mutter Gottes geweiht wurde. 1361 gab es den Namen Aicha noch nicht, da hieß der Ort noch "Sanmariakirchen". Heute erinnert der Name des Ortsteils "Frauenholz" noch an das ursprüngliche Kirchenpatrozinium.
1726-1735 wurde unter dem adeligen Pfarrherrn Dr. Siegmund Roman Rudolf Hormayr auf Hortenburg das gotische Gotteshaus völlig umgebaut und im Stil des frühen Rokoko gestaltet. Der Münchner Hofbaumeister Johann Michael Fischer wurde zu Rate gezogen. Jakob Pawagner aus Passau hat wahrscheinlich den Bau ausgeführt.
Die prachtvolle Pfarrkirche wurde von Füstbischof Lamberg 1735 den Apostelfürsten Petrus und Paulus geweiht. Das Patrozinium wird am 29. Juni gefeiert.