Sheila McKechnie was born in Camelon, Falkirk, on 3 May 1948 to Hugh McKechnie, then a commercial traveller, and Christina (née Marshall). She studied politics and history at the University of Edinburgh, where she was a friend of Gordon Brown.
She was a member of the students' representative council, holding the posts of Secretary and 2nd Junior President. After graduating, she studied for an MA in Industrial Relations at the University of Warwick.