1794, November (pub): St. Vigeans' Kelpy
From the year 1699 to the year 1736, the sacrament of the Lord's Supper was never dispensed in the church of St. Vigeans in Angus, Scotland. The legend explaining this singular behavior (the sacrament being standard practice for all other churches of the time) was that the stones that built the church had been carried to the site by a "water-kelpy," and that the foundations of the church was supported upon large bars of iron that held the building above a lake of unknown depths beneath it. Given how long the practice of the sacraments had been delayed, it had become the popular belief among the town that the reason was that the church would be in danger of sinking into the lake below and drowning everyone inside if the sacraments were dispensed. It should also be noted that the 'water-kelpy' was a creature commonly associated with the Devil, which could easily be living in the lake under the church; I must suspect that the creature's fabled assistance in building the church probably helped the populace reach the conclusion that the sacraments were being avoided for a distinct reason.
This belief in the dangers of the sacraments being read had become so prevalient that on the day the sacracments were finally administered for the first time in the church (presumable in 1736 or 1737), several hundreds of the parishioners chose to sit on a hill about 100 yards from the church rather than attend the sacraments themselves. Luckily for those inside the church, it did not sink into a massive lake beneath it... and soon the story and the worry were both forgotten.
The above short tale constitutes the earliest mention of the Scottish monster called the 'ech uisge' ['water-horse'] or 'kelpie' that I have found, being that it was published in 1794. It doesn't say much about the beast, but it does show it associated with a lake (as they usually are), and the name 'water-kelpy' is a pretty clear mix of the currently known titles for the beast.