Die Geschichte der Kirche reicht weit zurück, so haben schon die Alemannen im 5. Jahrhundert auf den Grundmauern eines verlassenen römischen Gebäudes eine Holzkirche errichtet.

Ein fester Bau entstand dann im 8. oder 9. Jahrhundert und wurde um 1000 ersetzt. Als kurz darauf das Dorf Muttenz als Dinghof in den Besitz des Bistums Strassburg kam, wurde die Kirche dem Heiligen Arbogast geweiht und er wurde deren Schutzpatron.

In der Mitte des 12. Jahrhunderts liess ein Lehensträger die Kirche in romanischem Stil neu erbauen, der Bau wurde aber nie ganz vollendet.

Im Jahr 1356 zerstörte das grosse Basler Erdbeben auch Teile der Kirche. So stürzte die Nordwand und das Gewölbe ein und der Turm litt ebenfalls.

Ab 1359 begann der Lehensträger Konrad Münch-Löwenberg mit der Instandsetzung und Vollendung der Kirche. Daher findet man in der Kirche an verschiedenen Orten sein Wappen, bestehend aus dem Mönch und dem Löwen. Um 1420 erhöhte Hans Thüring Münch-Eptingen den Kirchturm und als Schutz für die Bewohner des Dorfes Muttenz wurde die Kirche als Refugium ausgebaut und mit einer Mauer umgeben. Im Jahr 1504 wurde das Kirchenschiff erhöht. 1630 erhielt das Schiff grössere Fenster und eine Empore, der Turm wurde um ein zusätzliches Geschoss erhöht und gelangte zu seinem markanten Spitzhelm.

Mitte des 19. Jahrhunderts wurde durch die Gemeindeversammlung von Muttenz der Abbruch der Befestigungsanlage beschlossen, jedoch dank des Einsatzes von denkmalbewussten Bürgern, besonders des Zürcher Kunsthistorikers Johann Rudolf Rahn, verhindert.