This paper presents a new record of naked barley from the Okhotsk cultural layers of the Hamanaka 2 archaeological site on Rebun Island, northern Japan. Calibrated ages (68% confidence interval) of directly dated barley remains suggest that the crop was used at the site ca. 440-890 cal yr AD. Together with the finds from the Oumu site (north-eastern Hokkaido Island), the recovered seed assemblage marks the oldest well-documented evidence for the use of barley in the Hokkaido Region. The archaeobotanical data together with the results of a detailed pollen analysis of contemporaneous sediment layers from the bottom of nearby Lake Kushu point to some kind of low-level food production including cultivation of barley and management of wild plant that complemented a wide range of foods derived from hunting, fishing, and gathering. This qualifies the Okhotsk culture as one element of the long-term and spatially broader Holocene hunter-gatherer cultural complex (including also Jomon, Epi-Jomon, Satsumon, and Ainu cultures) of the Japanese archipelago, which may be placed somewhere between the traditionally accepted boundaries between foraging and agriculture. To our knowledge, the archaeobotanical assemblages from the Hokkaido Okhotsk culture sites highlight the north-eastern limit of prehistoric barley dispersal. Seed morphological characteristics identify two different barley phenotypes in the Hokkaido Region. One highly compact type (naked barley) associated with the Okhotsk culture and a less compact type (hulled barley) associated with Early-Middle Satsumon culture sites. This supports earlier suggestions that the “Satsumon type” barley was likely propagated by the expansion of the Yayoi culture via south-western Japan, while the “Okhotsk type” spread from the continental RFE Region, across the Sea of Japan. After the two phenotypes were independently introduced to Hokkaido, the boundary between both barley domains possibly existed ca. 600-1000 cal yr AD across the island region.