All Saints' Church is the younger of the two Scottish Episcopal churches in St Andrews. For 150 years after the disestablishment of the Episcopal Church in the reign of William and Mary, there was no church building in St Andrews. The various meeting places used by the congregation included a private house called Priorsgate on South Street, and an outhouse on Westburn Lane. The restrictions on the Episcopal Church were relaxed after the death of Prince Charles Edward Stuart in 1788. In 1824 the foundation stone was laid of an Episcopal chapel on North Street, and this building was consecrated in 1825 and dedicated to St Andrew. By 1860 this building, with a maximum capacity of 220, was outgrown. The chapel was sold to the Free Church congregation in Buckhaven. The building was dismantled, the stones transported by sea to Buckhaven and rebuilt there. The present site of St Andrew's Church, in Queen's Terrace, was acquired, and the new building there was consecrated in 1869. In 1895 a member of its congregation, T. T. Oliphant, observed that the poor had great difficulty in obtaining seats at the morning service because of shortage of room and the custom of pew renting. An additional church was clearly necessary, and following the death of T. T. Oliphant in 1902 it was proposed that part of the new church should be a memorial to him.
The site at the corner of North Street and North Castle Street was chosen to enable the church to serve as a mission to the fishing community based in this part of the town. A temporary iron church from Spiers of Glasgow was consecrated in May 1903, and provided free seating for a congregation of 150. Meanwhile the Oliphant Memorial Fund had been started, and this provided the means to build a stone chancel. The foundation stone for the chancel was laid on 11 March 1907 and the completed chancel was consecrated on 2 November 1907. The temporary iron structure was moved into a new position to form the nave of the church. All Saints' became known at this time as 'The Bundle Kirk' because charitable parcels were distributed by the congregation.
At the end of the First World War Mrs Annie Younger, wife of Dr James Younger of Mount Melville, gave money for the completion and endowment of the church. More ground was bought around the church, and fisherfolk displaced from their houses were rehoused in St Gregory's Buildings overlooking the castle beach. The land made available was used to build the nave, chapel and baptistry of the church. other buildings including the rectory, a church hall for theatricals and film shows, a well-equipped gymnasium, a guide hall, women's and men's club rooms with a library and a billiard room, were either newly built or provided by alterations to existing buildings. In addition to the buildings Mrs Younger provided money for vestments, altar furnishings and church furniture, pulpit, font, and all details down to the provision of notice boards and flower bowls. Mrs Younger provided the buildings and endowments as a memorial to her daughter and son-in-law. A condition of Mrs Younger's endowment of the church was that the Eucharist would be the main morning service every Sunday.
The foundation stone was laid for the new nave in June 1920. In the same month Rev P. H. Wilson was installed as Priest in Charge and All Saints' became independent from St Andrew's Church. The service of consecration was held in the new building on 1 November 1923. In November 1930 All Saints' became an incumbency. The rectory, ready in 1939, was the last building to be completed. All the buildings provided by Mrs Younger have been retained by All Saints' Church, but some have changed use in the intervening years. Castle Wynd House, once the club rooms, is now let to students. The former guide hall is now the Ladyhead coffee shop and bookshop, run by volunteers from churches in St Andrews. The former gymnasium is let to a local amateur dramatic society for meetings and rehearsals.