An earlier church at Stenkvista dated from the late 11th or early 12th century and stood beside the old churchyard. It was a small building, originally only about five by seven metres, later extended. When it was demolished, a runestone (Södermanlands runinskrifter 111) was found beneath the floor and was subsequently moved to the south-west corner of the new churchyard, where it can still be seen.
The current church was built in 1794 to designs by Thure Wennberg, roughly 250 metres south-west of the old site. Parishioners were given brick salvaged from Eskilstuna Castle, which had burned in 1680 and was being demolished, though the church itself is built mainly of granite rubble rather than that brick. An inscription above the south entrance records the rebuilding in the third year of King Gustav IV Adolf's reign, 1794.
The church was completed as a single nave, without its tower. New designs for a tower were later obtained from the architect Carl Gustaf Blom Carlsson, and the tower was finished in 1846; the exterior has remained largely unchanged since. Originally the sacristy occupied the easternmost part of the church in the apse, but in 1964 a new sacristy was created beneath the organ loft, allowing the apse to become part of the main body of the church.
Several furnishings survive from the earlier medieval church, including a triumphal crucifix from around 1400 and a font dating from the 12th century. The church holds two bells: a smaller bell recast in 1743 by Johan Fahlsten and a larger one cast in 1776 by Johan Jakob Mårtensson.
The church's organ history is layered. An organ built in 1697 by Georg Woitzig of Stockholm, later enlarged, was moved here from Jäders kyrka in 1866. It was eventually replaced by new instruments in 1904 and 1942, before the present mechanical organ was built in 1963 by Jehmlich Orgelbau of Dresden, which retained the historic 1697 case front, given new pipework and a rückpositiv in 1964.