It is thought that a church built on this site was one of the first in the Grand Duchy of Lithuania and was the first in northeastern Lithuania in the times of Vytautas the Great, construction of which was sponsored by the Castellan of Vilnius, Kristinas Astikas, in 1406. A Roman Catholic parish was established in Vyžuonos prior to 1553. When Vyžuonos was ruled by Continental Reformed Protestants, the church became their house of worship and the most important pantheon of the Radvila family, the dukes of Biržai and Dubingiai. The church had to be solid and of masonry construction, because two voivodes of Vilnius who owned Vyžuonos, the Grand Hetmans Kristupas Radvila Perkūnas and his son Kristupas Radvila as well as their young children, were buried there. When the church was returned to the Roman Catholics in 1656 by decision of the Ukmergė castle court, the sarcophagi with the remains of the Radvila family members were moved around 1666–1668 to the Continental Reformed Protestant church that had been built in Kėdainiai, becoming the burial site for this family of nobles in the Grand Duchy of Lithuania.
The church was reconstructed in 1706, but burned in 1796 during a large fire throughout the town, with only the walls and the pulpit remaining. It was rebuilt in 1811. During its centuries-long history, the church was rebuilt and renewed on several occasions, and it took on its present-day appearance after its reconstruction in 1891–1892. At that time, at the initiative of the pastor, the Rev. Antanas Drukteinis, the church was expanded, a steeple was added, the Stations of the Cross were built, and the present-day 9-register organ was installed (restored around 2000). In 1912, the stone masonry wall was built to enclose the churchyard.
The present-day church is of Gothic style, of plastered masonry, with a single steeple, arranged in the shape of a Latin cross, with a triple nave and a five-walled apse. A visitor's attention is drawn to the stone inclusions in the facade of the apse, cemented into the side during the last reconstruction: a mythological stone, the so-called Žalčio Vyžo galva (the head of the Grass Snake Vyžas), and a stone cannonball, said to have fallen into Vyžuonos long ago after being fired from the cannon of a passing army. It is perhaps the only church which hosts the symbol of a pagan deity, and it has become a symbol of the coexistence of two cultures.
In the church interior, the intersecting vaulted arches of the naves and the choir loft together with the ribbing connect to the octagonal cross-sectional piers and pilasters. A starry arch with ribbing rises over the sanctuary. Intersecting arches rise over the chapels. Cylindrical arches rise over the basement.
Each year in July, the Feast of Saint Mary Magdalene is celebrated, quite a rare event in Lithuania.
The church is listed on the Registry of Cultural Heritage Properties.