Huddunges första kyrka var troligen en träkyrka. Denna ersattes under senare delen av 1200-talet eller början av 1300-talet av en stenkyrka.
I den nuvarande kyrkan finns en teckning från 1700-talet som visar den medeltida stenkyrkan. Den var en typisk uppländsk gråstenskyrka med vitkalkade väggar och svart spåntak med brant takfall. Kyrkans västra gavel hade en blindering (fördjupning) i form av riksäpplet.
Innertaket försågs med valv under 1400-talet. Det finns inga belägg för medeltida kalkmålningar, men i kyrkoarkivet finns en räkning från 1641 gällande målningar utförda av Anders målare. Det han målade var troligen bårder med kyrkliga sentenser och bibelspråk.
Medeltidskyrkan var i bruk fram till 1700-talets slut. Då dömdes den ut och socknen ålades att uppföra en ny. Medeltidskyrkan revs, omvandlades till ruin och kom med tiden att konserveras. På sina ställen är muren över två meter tjock.