The village of Stow has a long and notable history, which is closely linked to the traditions of the church, going back to medieval times. In old English, the word "Stow" means a holy or consecrated place. When the Scots conquered Lothian in 1018, the ancient church of St Mary of Wedale passed into the diocese of St Andrews (and hence into Midlothian). Throughout the Middle Ages, it was famous for being one of only three sanctuaries in Scotland where persons could find refuge in times of trial.

Stow was known then as "Stow in Wedale", and the name of Wedale described what is known today as the Gala Water. Various explanations have been given for the background to the name "Wedale" including "Valley of Woe" and the dale of the holy house to an abbreviation for the Celtic Goidel race, but the truth of this may lie in the mists of antiquity.

It has been claimed that Stow was the scene of one of the victorious battles won by King Arthur over the Saxons, and the story also goes that Arthur founded the first church, dedicated to the Virgin Mary, and endowed with fragments of the True Cross. A great boulder allegedly bore the footprint of the Virgin but this seems to have disappeared when the new (A7) road was constructed in 1818.

The remains of this chapel lie a mile south of Stow near St Mary's Well. In 2000, 

a new path was laid alongside the A7 to provide easy access to visitors, and the well was rededicated in an ecumenical service.

In 1242, a new church, also dedicated to St Mary, was built at the edge of the village and beside the Bishop of St Andrews'  palace. This was both a place of sanctuary and pilgrimage. The extension  of the Bishop of St Andrews' lands to include Stow was probably the reason  why the land from the watershed at Fala to Bowland was formerly part of  the county of Midlothian; as this was border country with its back to the  Lothians, such an arrangement could be seen as an anomaly, which was changed in 1972, when the lands became part of Selkirkshire.  

In the 15th century, a new church was built to the west of the Bishop's Palace using red ashlar. This was rebuilt in the 17th century, and boasted an outside stair giving access by a doorway dated 1660 to galleries on the north, east and west sides.

We are told that the "penitents' pillar" was pulled  down and the sackcloth removed by the "Inglishmen" in 1651. In 1652, the kirk session refused an application to contribute something for two women, upon whose corns the English army "did leigar"; but the session was unable to assist, as the parish had been 'frequently plundered' of late.  Session meetings took place two, three, or more times a week, beside the fixed meeting on Sundays. Cases of immorality regularly came before the session, but by 1705, not one case of scandal was presented to the elders. The date of 1771 can still be seen on the windows  of the remains of this building, which served as church until 1876, but has been disused since that time.

By 1873, there was a movement to provide a more adequate church for the parish and, as it was not found possible to build on the old site, the session took the decision to build on a new site. A new building, with a striking steeple, was erected on a raised mound slightly to the south of the village and dominating the curve of the valley to the north. Mrs Mitchell-Innes was a major benefactor and on the first Sunday in 1876, the church was opened for public worship. The church still stands in the same location today.

There is only one transept - on the west side; the pulpit stands opposite this under a rose-windowed gable. There are stained glass windows - Ruth and the parable of the Sower (c1875) and New Testament scenes flanked by the Stoning of Stephen and Paul in Athens (1912). The communion table and chairs also date from 1912 and were made by John Taylor of Edinburgh.

Originally, there was seating for 700, but in 1996 the pews to the south were removed to provide an open meeting place for fellowship after the service. Private family bays were also replaced during the 1990s.

The organ was built by Ingram & Co.

This is now the only church in Stow, but this was not always the case. In 1732, at the end of the ministry of James Douglas, there was a disputed succession, and the congregation split to form the United Presbyterian Church, which initially met in a disused malt barn, then in a purpose-built church in the Earlston Road. In turn, they were replaced in 1872 by a fine building and manse on the main road. The church was demolished in 1955, but the United Presbyterian manse, became the manse for the Parish Church which had hitherto been at Wedale House, beside the traditional site of the old Bishop's Palace.  That manse was sold in 2017 and a modern manse purchased near the restored railway station.

This was not the only secession, for in the Disruption of 1843, a Free Church congregation was formed, so a third church and manse  were erected in the village. This was situated in Craigend Road, and lasted until 1901, when the Free Church amalgamated with the United Presbyterian Church.