As per the History of Camelot, before the birth of the five kingdoms the land was in an endless cycle of bloodshed and war. Bruta, Camelot's first king, put an end to it when he gathered together the elders of each tribe and drew up plans for the lands to be divided in a way that each would rule over their land as they saw fit and respect the boundaries.
Merlin adds some made up extension to the story as follows: when Bruta was on his deathbed, he asked to be taken deep into the forest. There, with the last of his strength, he thrust his sword into a rock. If his lineage was ever questioned, this would form a test, for only a true King of Camelot could pull the weapon free. The stone was lost many years ago during the Great Purge. By pulling the sword out, Arthur (together with his people) is lead to believe that he is the true king of Camelot.
Merlin adds a further made up bit to the story as follows: when the sword was thrust into the stone, the ancient King foretold that one day it would be freed again at a time when Camelot needed it most. The man who freed it would unite the land of Albion and rule over the greatest kingdom the world has ever known. With this second part of the story,Arthur is lead believe that he is destined to be Albion's greatest king.