After the Reformation a fairly large part of the population of Vlissingen remained catholic and attended a hidden church in Middelburg. In 1778 the Vlissingen town counsil agreed to tolerate a similar church in Vlissingen, but this decision ignited the fury of protestant fanatics and the permission was withdrawn. Finally, in 1793 the first catholic mass since the Reformation could be held in a private house. Two years later protestant rule in the Netherlands formally ended and religious freedom was proclaimed. In 1805 the catholic community of Vlissingen moved to another house, which in 1858 was replaced by a new church in Neo-Gothic style, designed by Th. Molkenboer, the St. Jacobus de Meerdere.
As the St. Jacobus became too small, in 1905 plans were made for a second catholic church. In 1910 sufficient funds were available and architect A.A.J. Margry had been commissioned to design the new church. Margry designed a church in Neo-Romanesque style with a monumental two-tower front. The latter part was never built, and at first the nave was only two traves long and closed by a simple, almost undecorated facade with a round window. After the St. Jacobus was closed and demolished in 1938, the O.L. Vrouwe Rozenkrans became a parish church.
The church is a cruciform basilica with a wide central-isle and narrow side-aisles. The transept-arms and the choir all end in a semi-circular apse. In 1923 a chapel was added. Although the plot of land made it possible, the church was not oriented and the choir points towards the north-west. In 1936 the building was lengthened with three traves by architect J. van Velsen, who copied the style of the original parts but added a different facade with a big rose window. In 1944 and 1945 the building was damaged by artillery and a flood. Already in September 1945 the church could be used again. In 1965 the facade was changed once again, with the rose-window being replaced by the current three tall round-topped windows.