A few decades after the collapse of the Avar Khaganate (c. 822 AD), Hungarian invaders conquered the Carpathian Basin (c. 862–895 AD). The first Hungarian ruling dynasty, the Arpads played an important role in European history during the Middle Ages. King Bela III (1172–1196) was one of the most significant rulers of the dynasty. He also consolidated Hungarian dominance over the Northern Balkans. The provostry church of the Virgin Mary (commonly known as the Royal Basilica of Szekesfehervar) played a prominent role as a coronation church and burial place of medieval Hungarian kings. The basilica’s building and graves had been destroyed over the centuries. The only royal graves that remained intact were those of King Bela III and his first spouse, Anna of Antioch. These graves were discovered in 1848. We defined the autosomal STR (short tandem repeat) fingerprints of the royal couple and eight additional individuals (two females and six males) found in the Royal Basilica. These results revealed no evidence of first-degree relationship between any of the investigated individuals. Y-chromosomal STR profiles were also established for all the male skeletons. Based upon the Y-chromosomal data, one male skeleton showed an obvious patrilineal relationship to King Bela III. A database search uncovered an existing Y-chromosomal haplotype, which had a single-repeat difference compared to that of King Bela. It was discovered in a person living in an area close to Hungary. This current male line is probably related paternally to the Arpad Dynasty. The control region of the mitochondrial DNA was determined in the royal couple and in the remains of the inferred relative. The mitochondrial results excluded sibling relationship between the King and the patrilineal relative. In summary, we successfully defined a Y-chromosomal profile of King Bela III, which can serve as a reference for the identification of further remains and disputed living descendants of the Arpad Dynasty. Among the examined skeletons, we discovered an Arpad member, whose exact affiliation, however, has not yet been established.