The Nesseby Church is a long church with a narrower and lower-rising rectangular choir, adjoined to the nave on the east side. A steeple, which houses the entrance, is adjoined to the west side. The building was constructed using wooden materials, cogging jointed timber that is clad with vertical panelling. All of the churches in Northern Norway that are designed by Grosch are built in this fashion, except for the Tjøtta Church which is made of stone. On the exterior, turnbuckles lagged like pilasters divide the wall into fields. A high-positioned arched Neo-Gothic style window is situated on each field.

The Nesseby Church is situated on a magnificent and characteristic site, on a spit that juts into the north side of the Varanger fjord. The site along with the meagre vegetation makes the white painted church, with a grey slate covered roof, easily visible from a distance.