For about five centuries Arnhem's major church had been dedicated to St. Martinus. But when relics of St. Eusebius were brought into the town it was decided to build a new church at the same location. In 1452 duke Arnold of Egmond laid the first stone. In the next century and more the new building gradually replaced the, in parts still pre-Romanesque, St. Martinus. The current church is a big three-aisled cruciform church in Lower-Rhine Gothic style. Despite the long construction period it is surprisingly consistent in style. For most of it brick was used, with natural stone mainly used for the outside of the tower. Part of the outlines of the old St. Martinus have been made visible in the pavement near the choir.

The first parts that were built were the tower, the first three traves of the nave and the St. Eusebius chapel. The old church continued to be used, although ca. 1477 its tower had to make place for the remaing part of the nave and the Flamboyant south-porch (above, second picture). By that time the new tower, which in style is closely related to the towers of Tiel and Zaltbommel, was completed. In 1503 the side-aisles were lenghtened with chapels that run along the sides of the tower.

The second stage was the construction of the choir and ambulatory. Because the foundations of a planned but unfinished earlier choir were used this part of the church is a-symmetrical. Ca. 1511 the remaining parts of the St. Martinus were demolished. After that the transept was built. Judging by the way this puts the south-porch in shadow it appears like this part of the church was not in the original plans, but a sizable afterthought instead.
In 1578 the church is confiscated by the protestants who call it simply Grote Kerk ('great church'). From this period dates the addition of a north-porch in Classical style. An octagonal upper segment is added to the tower in 1650-1651, which however has not survived. Otherwise the first four centuries of protestant use are mostly a period of neglect and vandalism. The church underwent several major restorations later, beginning in the 1870's.
The biggest disaster in the history of the church is the Second World War. In 1944, during the Battle of Arnhem, the church burnt out completely. The south side of the nave is greatly damaged, although the porch is miraculously saved, while the crossing, transept and choir are damaged to a lesser extent. The weakened tower collapses when retreating German troops destroy the bridge over the Rhine.
From 1946 until 1961 the St. Eusebius is restored under the leadership of architect B.T. Boeyinga, who allows himself some artistic licence. Especially the modern sculptures on the tower and the flying buttresses (see picture below) by H.J. Vreeling, inspired by the work of Walt Disney and writer and comic strip-author Marten Toonder, meet with criticism. The tower is finished in 1964, higher than ever thanks to a modern octagonal upper segment by Th. Verlaan. This segment, which is made of natural stone around a concrete core, is designed in a style inspired by Gothicism. In 1994 an elevator was added inside.