In May 1852 a deputation headed by the Rev. Adam Cairns met Secretary of State for War and the Colonies Sir John Pakington on the issue of celebrating Presbyterian marriages in Gibraltar.
The foundation stone for this building was laid on the 6th October 1852 by Mrs, Grey, wife of the Captain of the Port, with the church opened for service on the 28th May 1854. At the time, there was large military presence on the Rock which included a number of Scottish regiments and the church was built through the efforts of the Presbyterians who wished to have their own place of worship.
The church has seating for 340, and is still furnished with the original pews, pulpit and baptismal font; a pipe organ was added in 1905/06. On the south wall are three stained glass windows of considerable beauty. However, these date from 1953 as the previous ones were lost during the Bedenham explosion of 27th April 1951. The present memorable triptych stained glass window depicts images of St Andrew, Christ and St Columba.
The north wall of the kirk is adorned with several regimental plaques of battalions who had connections with the Church.