"COLDSTREAM, a parish, containing a post and market town of the same name, on the southern border of Berwickshire. It is bounded on the east and south by the river Tweed, which divides it from England; and on other sides by the parishes of Eccles, Swinton, and Ladykirk ... The ancient name of the parish was Lennel or Leinhall; and the ruins of Lennel church stand on the north bank of the Tweed, 1½ mile distant from Coldstream. Eastward from this church, there was formerly a vilage called Lennel, which was so entirely destroyed in the Border wars, that the site of it is not now known. According to Chalmers, the parish of Leinhall appears in charters as early as the year 1147 ... In 1716 a new parish-church was built at the village of Coldstream, and the designation of the parish was afterwards taken from the kirk-town."
From the Imperial Gazetteer of Scotland, edited by John Marius Wilson, 1868.
The parish church (Church of Scotland) has registers dating from 1690. Old Parish Registers (before 1855) are held in the National Records of Scotland in Edinburgh, and copies on microfilm may be consulted in local libraries and in LDS Family History Centres around the world. Later parish registers (after 1855) are often held in the National Records of Scotland as are any records of non-conformist churches in the area (often unfilmed and unindexed, and only available there).
Coldstream was another place on the Border (like Lamberton Toll and Gretna Green) where irregular marriages were regularly conducted (for more information on such marriages see the Church Records section of the Berwickshire page). Original Indexes has published a microfiche edition of a late 19th century transcript of a register for Coldstream Bridge, covering the years 1793-1797. 635 marriages are listed, including parishes of abode.