The original church was built in the 11th century by Bishop Donat and was dedicated to St. Nicholas of Myra, the patron saint of sailors. It received its name during the early 14th century, when the parish of St. Nicholas was extended outside the city so as to include the Manor of St. Sepulchre and the Deanery of St Patrick. The parish was divided into two parts: St. Nicholas Within the Walls and St. Nicholas Without.
The church fell into disrepair in the 17th century, and was rebuilt in 1707. By 1835 it was again having problems, and it was unroofed, although a chapel in the church, St. Mary’s, continued to be used until 1847. It was planned to demolish the church and build a new one. However, this was never done, and the parish united with that of St. Audoen in 1867.
The greater part of the graveyard was taken over by Dublin Corporation when building the Tholsel nearby. To accommodate Street alignment to Christchurch Place in the 20th century, the remains of the facade were moved back several feet.