He was born on 3 March 1790 at Yetholm, Roxburghshire to Margaret Herbert, of a Northumbrian family, and George Story, a parish schoolmaster.
After receiving elementary education at home he entered the University of Edinburgh in 1805, associating with Thomas Pringle, the son of a neighbouring farmer.
One of his tutorial posts was in the family of Lord Dalhousie, his youngest pupil being James Andrew Broun Ramsay, whose friendship continued through life.
Story defended his friend and neighbour, John McLeod Campbell of Row, who was deposed in 1831 by the General Assembly of the Church of Scotland for his views on the Atonement.
In 1830 his parishioner Mary Campbell professed to have received the gift of tongues; and, though Story exposed her imposture, she found disciples in London, and was given credence by Edward Irving.