Walter was a younger son of Walter Stewart, 3rd High Steward of Scotland, and his wife Beatrix of Angus, daughter of Gilchrist, Earl of Angus. In 1258-59, Walter accompanied Louis IX of France on his Crusade, according to tradition. After the death of King Alexander II of Scotland he was aligned with the "English faction", and in 1255 secured the persons of the young King and Queen, but he was not at this time allowed to a share in the government. About 1260, when Isabella, Countess of Menteith and her husband Walter Comyn, Lord of Badenoch were forced to leave Scotland, the magnates of Scotland arranged the marriage of her sister, Mary, Countess of Menteith, to Walter Stewart, who took possession of the lands and title, with questions of legal ownership being reserved. He was certainly using the title of earl ("jure uxoris") before 17 April 1261, when he was witness to a grant to the Paisley Abbey.