This study investigates the genetic structure of the present-day inhabitants of Beringia in order to answer questions concerning their origins and evolution. According to recent studies, the ancestors of Native Americans paused for a time in Beringia, during which they differentiated genetically from other Asians before peopling the New World. Furthermore, the Koryaks of Kamchatka share a "ubiquitous" allele (D9S1120) with Native Americans, indicating they may have descended from the same ancestral Beringian population that gave rise to the New World founders. Our results show that a genetic barrier exists between Kamchatkans (Koryaks and Even) and Bering Island inhabitants (Aleuts, mixed Aleuts, and Russians), based on Analysis of Molecular Variance (AMOVA) and structure analysis of nine autosomal short tandem repeats (STRs). This is supported by mitochondrial DNA evidence, but not by analysis of Y chromosome markers, as recent non-native male admixture into the region appears to have partially obscured ancient population relationships. Our study indicates that while Aleuts are descended from the original New World founders, the Koryaks are unlikely to represent a Beringian remnant of the ancestral population that gave rise to Native Americans. They are instead, like the Even, more recent arrivals to Kamchatka from interior Siberia, and the "ubiquitous" allele in Koryaks may result from recent gene flow from Chukotka. Genbank accession numbers for mtDNA sequences: GQ922935-GQ922973.