Den första kyrkan i Fresta var antagligen av trä fram till 1200-talet, då det i stället byggdes en gråstenskyrka. I väggarna finns tretton runstenar inmurade. Koret och sakristian är uppförda i romansk byggnadsstil. Långhuset och ett sidovapenhus tillkom på 1400-talet. Detta vapenhus blev senare borttaget. Något torn fanns inte. Klockorna hängde i en stapel av trä ett stycke från kyrkan där det tidigare församlingshemmet ligger. År 1776 genomfördes en omfattande restaurering, då även det nuvarande klocktornet tillkom.
Den gamla dopfunten av sten och det lilla processionskrucifixet av lind eller al från 1200-talets första hälft finns ännu bevarade i kyrkan. Krucifixet är format i romansk stramhet, men saknar sitt ursprungliga kors.
Figurmålningarna på väggarna har tillkommit vid 1400-talets mitt och kan identifieras med den sk. Strängnässkolan. Strängnäs domkyrka anses vara dess huvudmonument. På östra väggen inleder inleder aposteln Petrus med sin nyckel den apostoliska trosbekännelsen och på samma vägg avslutar aposteln Paulus trosbekännelsen med orden: ”…och ett evigt liv. Amen”.
Det senmedeltida altarskåpet från omkring 1470 är inte placerat på sin ursprungliga plats på högaltaret eller ett sidoaltare utan hänger på kyrkans sydvägg. Det har länge ansetts vara ett nordtyskt arbete men kan också vara tillverkat i Mälardalen. På utsidan av altarskåpets vänstra flygeldörr återfinns bland annat Gregorii mässa, där Kristus uppenbarar sig på altaret för påven Gregorius, en av de fyra latinska kyrkofäderna.
En ny orgel, tillverkad av Christensen & Söner från Danmark invigdes 1982. Samma företag har också installerat en mindre kororgel i kyrkan. (Kororgeln flyttades till Bollstanäs församlingshem 2022)
I Fresta kyrka har sedan 1788 funnits en gammal barockorgel. Denna orgel restaurerades år 2001 och är sedan dess i spelbart skick, återinvigd och tagen i bruk. I samband med restaureringen har den av tillgänglig expertis bedömts vara tillverkad 1697 istället för år 1720, som tidigare antagits.