1. The Earliest Lords
Stokesley as a settlement began far back in history, and our earliest record of it seems to be in Domesday Book, a description of England ordered by William the Conqueror and carried out in 1086. The account given of Stokesley records two Lords of the Manor with Anglo-Scandinavian names:
Havarthr , who was lord in 1066, when William first claimed the English throne, and
Uchtred, who was the lord when the survey was made.
We know little about either of these men, except that they were minor noblemen in the service of the King, and that both of them held other lands as well. Havarthr had lost all his lands by 1069, as a passage in Domesday tells us that all Havrthr's land was in the hands of the Sheriff (a royal official) in that year. Perhaps Havarthr had died or been killed in the battles of 1066, or perhaps he had been stripped of his land for disloyalty. At any rate, Uchtred was Stokesley's lord in 1086. It may have been one of these men who built the church and the mill in Stokesley that Domesday Book records.
2. The Baliol Family

The manor of Stokesley is said by Ord in his History and Antiquities of Cleveland to have been granted to Guy de Baliol in 1093, but this is a guess based on the assumption that Guy received it at the same time as his Northumberland and Durham lands. Later Baliols clearly did not know when the family became possessed of Stokesley, as, during the reign of Edward I, one claimed that the Baliols had held it with the right to hold a weekly market there ever since the conquest. This is clearly wrong. Domesday Book, compiled in 1086, makes no mention of the Baliols at all, and records the Lord of Stokesley in 1086 as Uchtred, a King's thegn.
In fact, the first concrete evidence of the Baliols at Stokesley comes from the reign of Henry I (1100 - 1135), and takes the form of a Charter recording the gift of the Parish Church and one carucate of land to the Abbot and monks of St Mary's Abbey York. The Charter names this Abbot as Richard, who was in office from 1112 to 1122. Towards the end of the document, Guy asks for God's blessing on various members of his family, and it is noteable that he mentions no children of his own, but does mention his nephew Bernard.
Bernard de Baliol, famous as the builder of Barnard Castle in County Durham, nephew of Guy, succeeded to Guy's lands by 1130, when he was assessed for tax on it. The Baliols became crucial to the defence of the north, engaging in wars against the Scots. Bernard himself played a crucial part in the Battle of the Standard in 1138 when the forces of King David were routed by the English near Northallerton.
Baliols held the Lordship of the Manor of Stokesley for a hundred years or more, until Hugh Baliol granted it as part of the dowry of his daughter Ada on her marriage to John FitzRobert de Eure around 1220. We have no firm date for the marriage, but Ada was born about 1204, and she is said to have been buried near the high altar of Stokesley Parish Church. Ada's brother John was the founder of Baliol College, Oxford, and a few year later the Baliol family even supplied a claimant for the Scottish Crown, another John Baliol. When King Edward I was asked to choose between the rival claimants he chose John to be King of the Scots. (Baliol was an unpopular choice, and the Scots soon overthrew him)
Even after this, the Baliols continued to hold Stokesley from the King, but in gifting the town to John FitzRobert de Eure they had given to him and to his heirs the title of Lord of the Manor of Stokesley.
3. The Eure Family
John FitzRobert de Eure was the first Eure to be Lord of Stokesley. The Eure family is said to have come to England with William the Conqueror and to have taken its name from the family estate of Iver in Buckinghamshire, but the most important Eure estates in Yorkshire were those of Malton.
Nevertheless, Stokesley's development seems to have made huge strides under the Eures. The right to hold an annual FAIR in Stokesley was granted by Henry III to John FitzRobert in the year 1223-4, a Charter to this effect being issued by the young King. Another charter later in the reign moved the time of the fair to Trinity (around Easter time) and these two charters together show that the Eures were trying to make a real financial success of their new possession. It is likely that it was in John FitzRobert's time that the High Street was laid out and that the town took on the fundamental shape that it retains to this day, with the two greens at either end of the main road through the town (now known as West Green and College Square).