Its '5/8-Schluss' choir dates to the Gothic period - this style is named after the eight segments to the vaults in the five east-end arches.
The church was dedicated the Virgin Mary, St Martin of Tours and Elizabeth of Hungary.
The stift was set up in 1366-67 and Pope Urban V confirmed a new construction phase to provide a parish church whilst the quire was handed over to the canons.
Several of the church's canons took offices at the Hessian court in the period running up to the Reformation.
During his time as king of Westphalia, Jérôme Bonaparte tried to transfer the seat of the Paderborn Archdiocese to Kassel and make the Martinskirche into a cathedral, but his brother Napoleon I prevented him.
At the end of the 19th century the unfinished building was redesigned and completed by the architect Hugo Schneider (builder of the Luther Church).
During the raid on 22 October that year, the sandstone walls of the church were so badly damaged that they had to be repaired with shotcrete and a wooden lattice-work.