Hjälsta kyrka är från 1400-talet, och är därmed ganska ny med traktens mått mätt. Tidigare fanns två socknar med egna kyrkor (Tunbo socken med kyrka i nuvarande Tuna och Hjälsta socken med kyrka i Skönsberg vid Hjälstaviken), och när socknarna slogs samman på 1400-talet byggde man en ny gemensam kyrka. Enligt legenden ska platsen för kyrkan har valts ut efter ett snöfall vid midsommar som pekade ut platsen för kyrkans placering. Stenar till kyrkbygget kan enligt historien ha rullats från den äldre kyrkan vid Hjälstaviken upp till den nya platsen.
Kyrkan ligger på en höjd och har vackra höga stjärnvalv – enligt uppgift de högsta i någon landsortskyrka mellan Stockholm och Stora Tuna i Dalarna. Kyrkans dopfunt är från 1200-talet och stod i en av de två tidigare kyrkorna och kyrkans triumfkrucifix är från 1400-talet. Till kyrkans invigning i slutet av 1400-talet beställdes också flera altaren och träskulpturer - intressant är att mycket av räkenskaper har bevarats så att vi får veta ovanligt mycket om ett medeltida kyrkobygge.
Hur länge interiören i den medeltida kyrkan finns kvar intakt vet vi inte, men inte förrän på 1700-talet nämns några större inköp, som exempelvis då en altaruppsats köps in 1707 för att ersätta det medeltida altarskåpet. Under 1700-talet byggdes läktaren, och nya bänkar kom på plats. I princip inget av detta finns kvar idag, eftersom kyrkan år 1895 genomgick en grundlig förändring. i samband med att Hjälstaholms pastorat bildades av församlingarna Hjälsta, Kulla, Fittja och Holm och Hjälsta blev huvudkyrka. Då köptes predikstolen från Fittja kyrka (som blev ödekyrka) och ett stort korfönster i öster försågs med glasmålningar och ett nytt kors uppsattes på altaret. Den gamla predikstolen, altaruppsatsen och bänkarna såldes - altaruppsatsen finns idag i Björkviks kyrka i Sörmland.
Vid förändringarna vid 1800-talets slut togs även dopfunten från 1200-talet bort från kyrkan, men den fick komma in igen i samband med att ärkebiskop Nathan Söderblom visiterade församlingen 1925. 1925 hängdes även ett triumfkrucifix från medeltiden, som bevarats i sakristian, upp igen inne i kyrkan.
Vid en renovering 1952-55 gjordes några ytterligare förändringar, och bland annat flyttades det kors som sedan 1895 stått på altaret till sin nuvarande plats längst ned i kyrkan. I stället finns i koret nu ett altarskåp med oljemålningar av konstnären Marianne Nordström, kanske mera känd som syster Marianne i Alsike kloster. 1955 återinvigdes kyrkan efter renoveringen och hade då fått nya bänkar efter gammal förlaga samt även en ny kormatta.