This paper discusses archaeobotanical remains of naked barley recovered from the Okhotsk cultural layers of the Hamanaka 2 archaeological site on Rebun Island, northern Japan. Calibrated ages (68% confidence interval) of the 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 low-level food production, including cultivation of barley and possible management of wild plants that complemented a wide range of foods derived from hunting, fishing, and gathering. This qualifies the people of 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 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 Russian Far East 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. Despite a large body of studies and numerous theoretical and conceptual debates, the question of how to differentiate between hunter-gatherer and farming economies persists reflecting the wide range of dynamic subsistence strategies used by humans through the Holocene. Our current study contributes to the ongoing discussion of this important issue.