Gundsømagle kirke hører til blandt landets ældste romanske kirker. Den blev grundlagt tidligt i 1100-erne med kor, skib og apsis. Sidstnævnte blev dog fjernet o. 1450. Den nedre del af det gotiske tårn blev bygget 1320, mens de øvre stokværk er fra 1500-tallet. Oprindelig var der fladt loft i skib og kor, men dette ændredes, da hvælvene kom til midt i 1400-tallet, først i koret siden i skibet. Ved samme lejlighed ændredes taghældningen, og taget blev lidt højere, så der blev plads til hvælvene. Som i alle romanske kirker var der en kvindeindgang i nordsiden af skibet. Konturerne af denne dør og de oprindelige romanske vinduer sås meget tydeligt under reparation af nordmurens pudslag i 1985. Tilmuringen skete sandsynligvis da hvælvene blev bygget. Det romanske vindue i korets nordside genetableret i 1991. Mandsindgangen med våbenhuset på skibets sydside bevaredes indtil slutningen af 1800tallet. Det oprindelige våbenhus ændredes til kapel, og kirkens indgang flyttedes til vestsiden af tårnet.

I tårnet hænger to klokker. Den største er fra 1705, mens den mindste er fra 1751 dog omstøbt i 1903. I 1899 afdækkede og reparerede J. Kornerup nogle kalkmalerier i korbuen. Senere blev der også afdækket et mindre parti kalkmalerier på skibets nordside.