Many studies of the medieval Black Sea address the importance of Byzantine imperial agency in facilitating economic and political exchange. However, few studies examine the limits of Byzantine statehood regarding trans-Black Sea local dynasts. This study, primarily utilizing sigillography, focuses on the eleventh-twelfth century notable families of Cherson and Trebizond in case studies, particularly the well-known Tzouloi and Gavrades: two cities and families famed for their respective local autonomies. How can seals uncover an otherwise hidden dimension of Byzantine sovereignty, or its contestation, which manifested itself across the Black Sea even before the emergence of the empire of Trebizond after 1204?