The oldest parts of Vaksala Church, the tower and the western end of the church, were erected during the 12th century. Today the church is located in the outskirts of Uppsala city, but at the time of its construction – before the establishment of the Diocese of Uppsala - the church was the centre of one of the hundreds of Uppland, close to the location of a thing and by a locally important road. A guild operated in the locality throughout the Middle Ages.
Throughout the Middle Ages the church was expanded and rebuilt. The barrel vaulted vestry was added during the 13th century; during the same century a new and larger choir was built. The church was further enlarged and changed internally during the 14th century. During this time the church started to acquire its present, largely Gothic look, replacing the older Romanesque edifice. During the 15th century, two chapels were added to the church.
The church spire dates from 1692 but seems to have replaced an older one of the same design. The exterior of the church was altered in 1810, when the crow-stepped gables that had adorned all the church's gables since the Middle Ages were removed. In 1929 a renovation was carried out, and another one in 1969.
The exterior of the church is largely Gothic in appearance, but contains remains of the first, Romanesque church as well as a few later alterations. It is built of granite and brick. As for the interior of the church, it is a single-aisled church with two side-chapels and without an apse. The side chapels are unusual in that they were vaulted already during the 14th century; most of the churches in the vicinity did not receive proper brick vaults until the 15th century. The interior of the church is decorated with frescos dating from several periods, some possibly made by Albertus Pictor. They were covered in whitewash during the 18th century and laid bare again during the 20th century but remain somewhat damaged. Among the furnishings, the unusually large, 16th-century carved and gilded altarpiece made in Antwerp merits special mention. It is one of the largest of its kind in Sweden. There is also an unusual preserved Romanesque bench. A lot of the furnishings date from the 18th or 19th centuries; the façade for the organ is from 1805 and designed by Olof Tempelman.
In the close vicinity to the church, a brick building dating from the 15th century and which may have served as a storage or, possibly, housed the local guild. A runestone, the so-called Vaksala Runestone, stands in the churchyard.
- "Vaksala kyrka" (in Swedish). Upplandia.se. Retrieved 17 October 2013.
- "Vaksala kyrka" (in Swedish). Church of Sweden. Retrieved 17 October 2013.
- Qviström, Linda; Anund, Johan (2012). Det Medeltida Uppland. En arkeologisk guidebok (in Swedish). Lund: Historiska Media. pp. 205–207. ISBN 978-91-85873-74-6.
- "Vaksala kyrka" (in Swedish). Uppsala.com. Retrieved 17 October 2013.