There are longstanding questions about the origins and ancestry of the Picts of early medieval Scotland (ca. 300–900 CE), prompted in part by exotic medieval origin myths, their enigmatic symbols and inscriptions, and the meagre textual evidence. The Picts, first mentioned in the late 3^rd century CE resisted the Romans and went on to form a powerful kingdom that ruled over a large territory in northern Britain. In the 9^th and 10^th centuries Gaelic language, culture and identity became dominant, transforming the Pictish realm into Alba, the precursor to the medieval kingdom of Scotland. To date, no comprehensive analysis of Pictish genomes has been published, and questions about their biological relationships to other cultural groups living in Britain remain unanswered. Here we present two high-quality Pictish genomes (2.4 and 16.5X coverage) from central and northern Scotland dated from the 5^th-7^th century which we impute and co-analyse with >8,300 previously published ancient and modern genomes. Using allele frequency and haplotype-based approaches, we can firmly place the genomes within the Iron Age gene pool in Britain and demonstrate regional biological affinity. We also demonstrate the presence of population structure within Pictish groups, with Orcadian Picts being genetically distinct from their mainland contemporaries. When investigating Identity-By-Descent (IBD) with present-day genomes, we observe broad affinities between the mainland Pictish genomes and the present-day people living in western Scotland, Wales, Northern Ireland and Northumbria, but less with the rest of England, the Orkney islands and eastern Scotland—where the political centres of Pictland were located. The pre-Viking Age Orcadian Picts evidence a high degree of IBD sharing across modern Scotland, Wales, Northern Ireland, and the Orkney islands, demonstrating substantial genetic continuity in Orkney for the last ~2,000 years. Analysis of mitochondrial DNA diversity at the Pictish cemetery of Lundin Links (n = 7) reveals absence of direct common female ancestors, with implications for broader social organisation. Overall, our study provides novel insights into the genetic affinities and population structure of the Picts and direct relationships between ancient and present-day groups of the UK.