Okjeo war ein kleiner Stammesverbund, der vermutlich im 2. Jahrhundert v. Chr. im Zuge des Untergangs Go-Joseons gegründet wurde. Aufgrund seiner Lage zwischen mächtigeren Nachbarn konnte sich wahrscheinlich nie eine starke zentrale Regierung herausbilden. Es wurde schließlich im frühen 5. Jahrhundert n. Chr. von Goguryeo erobert.
Dong-Okjeo („Ost-Okjeo“) befand sich wahrscheinlich im Gebiet der heutigen nordkoreanischen Provinz Hamgyŏng. Buk-Okjeo („Nord-Okjeo“) - in manchen Quellen auch Chiguru ((置溝婁; 치구루) oder Guru (구루) genannt - lag am Ufer des Tumen-Flusses. Im Süden grenzte Okjeo an Dongye.
Im 1. oder 2. Jahrhundert n. Chr. reduzierte König Taejo von Goguryeo Okjeo zu seinem Vasallenstaat, das Waren an Goguryeo liefern musste. Während der Invasion der chinesischen Wei-Dynastie im Jahr 244 n. Chr. zog sich Goguryeos König Dongcheon kurzfristig nach Buk-Okjeo zurück. 285 n. Chr. suchte der Königshof von Buyeo in Okjeo Schutz vor Angriffen nomadischer Stämme aus dem Norden.
Im frühen 5. Jahrhundert eroberte König Gwanggaeto von Goguryeo Okjeo.