In May 1891, a meeting was held in the town of Innerleithen, during which a decision was made to form a football club. In the Scottish Borders, Selkirk FC had been formed in 1880, followed by Berwick Rangers and Duns the following year, and the brothers R & W Hume who had come to Innerleithen from Selkirk had a big hand in the founding of the club.

It took time to negotiate for a field to play on, but eventually one was found opposite the town's slaughter house. A pitch was marked out, a wooden hut erected to act as changing rooms and the field was given the name Caddon Park.

The new club played their first match on the 8th of October 1891 against Gala Harp and won 2-1. The next week they played Peebles Hibs and lost by three goals to two. Those first two games were played under the name 'Leithen Vale', but the name was then changed to 'Vale of Leithen F.C.' The reason for this choice of name is obscure - one theory is that the club Vale of Leven, based in Alexandria, Dumbartonshire and who were playing in the Scottish League at the time may have influenced the decision, but 'Vale' means valley and Leithen Valley has long been referred to as the Vale of Leithen in local publications.

The first club Secretary was Mr A. Brunton, who was succeeded in 1893 by Mr Alexander Crabbe who was originally from Dundee and had come to Innerleithen to take up employment at Robert Smail & Sons Printing Works.