William White rebuilt most of the church in 1869. Church is comprised of a W tower with 13thc. bell openings, a four-bay nave with N aisle, and a chancel; 18thc. doorway into nave. Reused Romanesque sculpture fragment in nave wall.

Though North Kelsey is mentioned in the Domesday Survey, there is no record of a church here in 1086. King Stephen granted North Kelsey to the church of Lincoln as a prebend in a charter of c. 1140. The N aisle of the church was a gift of John Wyga in 1372 (see Owen).

Pevsner lists the church dedication here as St Nicholas, but at the church the dedication is clearly All Hallows. The Diocesan directory of Lincoln lists both names as titular dedications. Without taking a position, Pevsner notes that L. Butler has suggested that this fragment of carved stone is a reused grave slab. The tapering dimensions of the stone support Butler's conclusion.