Although the title first appears in a document of 1049, where Domenico I Contarini, the Doge of Venice, uses it alongside the title of patrikios to refer to himself, it is commonly accepted that it was created by Emperor Alexios I Komnenos (r. 1081–1118). It was first conferred to his brother Adrianos, while another early holder, his brother-in-law Michael Taronites, was soon after raised to the even higher title of panhypersebastos. It was also conferred on Sergius VI of Naples and his son, John VI, at about the same time.
Later, during the 12th century, it was given to close relatives of the Byzantine emperor, such as the eldest son of a sebastokratōr. In the Palaiologan period it was conferred to leading aristocratic families, such as the Tarchaneiotai, the Raoul, etc.
The Book on Offices by Pseudo-Kodinos, written shortly after the middle of the 14th century, places the prōtosebastos in the thirteenth place in the overall hierarchy after the emperor, between the megas logothetēs and the pinkernēs. His ceremonial costume comprised a golden-green skiadion hat with silk embroideries, or a domed skaranikon in a reddish apricot colour decorated with gold-wire embroidery, with a painted glass depiction of the emperor standing in front, and enthroned in the rear. A rich silk kabbadion tunic was also worn.
- Adrianos Komnenos, brother of Alexios I Komnenos
- Alexios Branas, general
- Alexios Komnenos, nephew of Manuel I Komnenos, de facto regent in 1180–82
- Constantine Bodin, ruler of Duklja in 1081–1101
- George Mouzalon, friend and chief minister of Theodore II Laskaris
- Hrelja, magnate of the Serbian Empire
- John Komnenos, nephew of Alexios I Komnenos and governor of Dyrrhachium
- Michael Panaretos, official and historian of the Empire of Trebizond
- Philaretos Brachamios, general
- Kazhdan, Alexander, ed. (1991). The Oxford Dictionary of Byzantium. Oxford and New York: Oxford University Press. ISBN 0-19-504652-8.
- Magdalino, Paul (2002) . The Empire of Manuel I Komnenos, 1143–1180. Cambridge: Cambridge University Press. ISBN 0-521-52653-1.
- Stiernon, Lucien (1965). "Notes de titulature et de prosopographie byzantines: Sébaste et gambros". Revue des études byzantines. 23: 222–243. doi:10.3406/rebyz.1965.1349.
- Verpeaux, Jean, ed. (1966). Pseudo-Kodinos, Traité des Offices (in French). Centre National de la Recherche Scientifique.
- von Falkenhausen, Vera (2007). "The South Italian Sources". Proceedings of the British Academy. 132.