Kyrkan är tornlös och har en oklar tillkomsthistoria. Redan på 1200-talet omtalas Templum Omnium Sanctorum i skrift. I slutet av 1500-talet ombyggdes kyrkan till sitt nuvarande utseende, med tre skepp. Lite senare tillkom det nuvarande koret. Det Tungelskagravkoret tillkom på 1660-talet. År 1665 eldhärjades kyrkan, varefter kalkstenskolonnerna täcktes med tegel. Vid den restaurering som kyrkan genomgick åren 1959–1960 under ledning av arkitekt Erik Lundberg, återställdes kolonnerna i långhuset genom att de brandskadade kalkstensblocken ersattes med nyhuggna.
Klockstapeln, det närbelägna Östra klocktornet, förstördes i en brand 2 juni 2017.[1]
Inventarier
Altaruppsatsen i praktfull barock är ett verk av bildhuggaren Niclas Enander och skänktes 1674 till kyrkan av änkefru Maria Elisabet Kurtzel på Sjösa.
Predikstolen är troligen även den ett verk av Niclas Enander och sannolikt bekostad av ståthållaren Nils Tungel och hans hustru Brita Örnehufvud på Ånga.
Orglar
1690 reparerades ett orgelverk.
1709 köptes ett positiv från Ånga herrgård. Orgeln har 4 bälgar. Har under åren förbättrats. Orgeln fanns fram till åtminstone 1773.
I närheten av Alla Helgona kyrka låg tidigare franciskanerklostret Nyköpings konvent. Dess altarskiva har blivit funnen och fungerar idag som altarskiva i Franciskuskapellet, beläget i stadsdelen Rosenkälla, som tillhör församlingen.
^Abrahamsson Hülpers, Abraham (1773). Historisk Afhandling om Musik och Instrumenter särdeles om Orgwerks Inrättningen i Allmänhet jemte Kort Beskrifning öfwer Orgwerken i Swerige. Västerås: Johan Laurentius Horrn. sid. 218-219. Libris2413220