Johnstone comes from "John's toun", not "John's stone" or John's son." Historically, "Johnston" has been an alternate spelling of the surname. The first known person of this name was John of Johnstone, who in 1174 gave his name to the lands of Annandale in Dumfrieshire which he had been granted. His son, called Gilbert Johnstone ("Gillibertus de Johnistoun") appears on records between 1194-1214 and onwards, presumably taking his surname from the town his father had established - "Johnstone" or "John's toun".
Gilbert's Grandson called Sir John Johnstone was a Knight of the county of Dumfries. Sir John Johnstone signed the Ragman Roll of King Edward I of England in 1296.
At this time Perth was known as St Johnston and Johnstonburn in East Lothian was then called Jonystoun. These two areas have records of the Johnstone Clan. A third area of Johnstones which came from Stephen the Clerk and Margaret the heiress of Sir Andrew Garioch used the family name of Johnston.
Sir John Johnstone, grandson of the aforementioned Sir John, was a highly active leader on the border and resisted the English quite well from 1377 through 1379. He fought against the English armies at the Battle of Solway in 1378. The Johnstones were also at the Battle of Otterburn in 1388. In roughly 1218, William Wallace gave the Lochmaben castle to Johnstone of Eskdale, who apparently was his kinsman.
It was the fighting Johnstons of the Western Borders who would become most powerful group of Johnstons in Scotland. The elder Sir John's great grandson Adam (son of the younger Sir John) was Laired of Johnston in around 1413. In 1448 Adam and the Johnstons took part in the victorious fight against the English at the Battle of Sark during the Anglo-Scottish Border Wars. 
Adam's son supported King James II of Scotland in putting down the Clan Douglas. They won their lands of Buittle and Sannoch near Threave Castle as a reward.
John Johnstone the eldest son of Adam was progenitor of the Annandale branch and his brother Matthew who married the daughter of the Earl of Angus was progenitor of the wester Hall branch of Johnstones. John's offspring would become the main chief Johnstone family.
Later in 1608, Maxwell's loss was avenged when a meeting took place between his son, the new Maxwell chief and Johnstone himself. Maxwell killed the Johnstone chief. However Maxwell was later captured and executed by hanging.
The Clan Johnstone also had a long feud with the Clan Moffat who were another Scottish border clan who were raiders and reivers, and conducted long-running feuds with their neighbours. Their greatest enemies were the Clan Johnstone. The feud climaxed with murder of the Clan Moffat chief in 1557, Robert Moffat. The Clan Johnstone then went on to burn the local church with the most important members of the Moffat family inside, slaughtering anyone who tried to escape. Thus, in one blow the powerful Clan Moffat was almost wiped out. Seventy years later all of the Moffat's lands were passed to the Johnstones due to the Moffats having massive debts.
During the Civil War, the Clan Johnstone supported the Royalist cause of King Charles. In 1633, King Charles I awarded lordship to the Johnstone chief, Sir James Johnstone, as the Lord Johnstone; ten years later Charles made him the Earl of Hartfell. After King Charles I was defeated in the Civil War, both the Johnstone chief and his eldest son were imprisoned in Dumbarton Castle and Edinburgh Castle. However, after the Stuart Monarchs returned to the throne, King Charles II rewarded the Johnstones' loyalty by granting Lord Hartfell the titles of Earl of Hartfell and Annandale, Viscount of Annan, and Lord Johnstone of Lochwood, Lochmaben, Moffatdale and Evandal.
By the 1700's the Clan Chief of Johnstones had been raised from the rank of Lord to Earl of Annandale and Secretary of State. John the second of the Wester Hall branch was made a Baronet of Nova Scotia.