Man tror att den första gårdskyrkan i Vallby byggdes som ett litet träkapell. Man vet dock att en stenkyrka måste ha uppförts på tidigt 1100-tal enligt en "normalplan" som vi kan finna i ett flertal av norra Södermanlands kyrkor.
Denna kyrka byggdes intill ett långhus som ett uppåt avsmalnande stentorn med kvadratisk plan vars storlek var 5 X 7 meter. I öster byggdes ett kvadratiskt kor så stort som tornets bottenvåning. Efter ett flertal utbyggningar och restaureringar står idag på denna plats en ståtlig kyrka med vitputsade väggar.