Stallingborough is recorded as a manor (as "Stalinburg" or "Stalingeburg") in the 11th century "Domesday Book". The medieval village of Stallingborough was to the west of the modern village, and south of the 18th century church. The rights to hold a market and annual fair were granted by Henry III (13th century). Before the Black Death of the mid 14th century, the village had 50–60 households. This substantially decreased after the plague, but recovered to around 150 households by the mid 16th century. The medieval village is evidenced by earthworks, as well as cropmarks of fishponds, remains of ridge and furrow farming to the north, and a medieval cross in the churchyard of the modern church.