The parish of Gresham sits in north-east Norfolk close to the North Sea coast but inland of the twin seaside resorts of Sheringham & Cromer. The parish sits in the lanes south of the main route across north Borfolk, the A148. The village has two distinct clusters of settlement, one on higher ground to the west of the church and a second in a shallow valley to the east. These two centres are joined by an east-west running lane.

All Saints church sits at a cross-roads midway between the two parts of the village, it is quite an old church with many Norman features including its round tower (though repaired and modified in Victorian times). There is also use of carrstone a material favoured by the older churches. Much else indicates that the church was substantially added to during the great Norfolk church building period of the 14th/15th centuries.