Mary Fleming (/ˈflɛmɪŋ/) (1542-fl. 1581), was a Scottish noblewoman and childhood companion of Mary, Queen of Scots. She and three other ladies-in-waiting (Mary Livingston, Mary Beaton and Mary Seton) were collectively known as "The Four Marys". A granddaughter of James IV of Scotland, she married the queen's renowned secretary, Sir William Maitland of Lethington.
Mary Fleming was the youngest child of Malcolm Fleming, 3rd Lord Fleming and Janet Stewart. She was born in 1542, the year her father was taken prisoner by the English at the Battle of Solway Moss. Her mother was an illegitimate daughter of James IV of Scotland, born during his marriage to Margaret Tudor. Lady Fleming became a governess to the infant queen, also born in 1542, and the dowager queen, Mary of Guise, chose Lady Fleming's daughter Mary to be one of four companions to the young queen. Mary Fleming and Mary, Queen of Scots, were technically half-first-cousins.
In 1548, five-year-old Mary Fleming and her mother accompanied Mary, Queen of Scots, to the court of King Henry II of France, where the young queen was raised. Mary Fleming's father having died the previous year in the Battle of Pinkie, her mother had an affair with the French king, the product of which was a son born around 1551.