，乌珠留若鞮单于子右奥鞬日逐王比自立为南单于，入居西河美稷，今离石左国城即单于所徙庭也。中平中，单于羌渠使子於扶罗将兵助汉，讨平黄巾。会羌渠为国人所杀，於扶罗以其众留汉，自立为单于。属董卓之乱，寇掠太原、河东，屯于河内。於扶罗死，弟呼厨泉立，以於扶罗子豹为左贤王，即元海之父也。魏武分其众为五部，以豹为左部帅，其余部帅皆以刘氏为之。太康中，改置都尉，左部居太原兹氏，右部居祁，南部居蒲子，北部居新兴，中部居大陵。刘氏虽分居五部，然皆居于晋阳汾涧之滨。
豹妻呼延氏，魏嘉平中祈子于龙门，俄而有一大鱼，顶有二角，轩鬐跃鳞而至祭所，久之乃去。巫觋皆异之，曰：“此嘉祥也。”其夜梦旦所见鱼变为人，左手把一物，大如半鸡子，光景非常，授呼延氏，曰：“此是日精，服之生贵子。”寤而告豹，豹曰：“吉征也。吾昔从邯郸张冏母司徒氏相，云吾当有贵子孙，三世必大昌，仿像相符矣。”自是十三月而生元海，左手文有其名，遂以名焉。龆龀英慧，七岁遭母忧，擗踊号叫，哀感旁邻，宗族部落咸共叹赏。时司空太原王昶闻而嘉之，并遣吊赙。幼好学，师事上党崔游，习《毛诗》、《京氏易》、《马氏尚书》，尤好《春秋左氏传》、《孙吴兵法》，略皆诵之，《史》、《汉》、诸子，无不综览。尝谓同门生硃纪、范隆曰：“吾每观书传，常鄙随陆无武，降灌无文。道由人弘，一物之不知者，固君子之所耻也。二生遇高皇而不能建封侯之业，两公属太宗而不能开庠序之美，惜哉！”于是遂学武事，妙绝于众，猿臂善射，膂力过人。姿仪魁伟，身长八尺四寸，须长三尺余，当心有赤毫毛三根，长三尺六寸。有屯留崔懿之、襄陵公师彧等，皆善相人，及见元海，惊而相谓曰：“此人形貌非常，吾所未见也。”于是深相崇敬，推分结恩。太原王浑虚襟友之，命子济拜焉。
咸熙中，为任子在洛阳，文帝深待之。泰始之后，浑又屡言之于武帝。帝召与语，大悦之，谓王济曰：“刘元海容仪机鉴，虽由余、日磾无以加也。”济对曰：“元海仪容机鉴，实如圣旨，然其文武才干贤于二子远矣。陛下若任之以东南之事，吴会不足平也。”帝称善。孔恂、杨珧进曰：“臣观元海之才，当今惧无其比，陛下若轻其众，不足以成事；若假之威权，平吴之后，恐其不复北渡也。非我族类，其心必异。任之以本部，臣窃为陛下寒心。若举天阻之固以资之，无乃不可乎！”帝默然。
后秦凉覆没，帝畴咨将帅，上党李憙曰：“陛下诚能发匈奴五部之众，假元海一将军之号，鼓行而西，可指期而定。”孔恂曰：“李公之言，未尽殄患之理也。”憙勃然曰：“以匈奴之劲悍，元海之晓兵，奉宣圣威，何不尽之有！”恂曰：“元海若能平凉州，斩树机能，恐凉州方有难耳。蛟龙得云雨，非复池中物也。”帝乃止。后王弥从洛阳东归，元海饯弥于九曲之滨。泣谓弥曰：“王浑、李憙以乡曲见知，每相称达，谗间因之而进，深非吾愿，适足为害。吾本无宦情，惟足下明之。恐死洛阳，永与子别。”因慷慨歔欷，纵酒长啸，声调亮然，坐者为之流涕。齐王攸时在九曲，比闻而驰遣视之，见元海在焉，言于帝曰：“陛下不除刘元海，臣恐并州不得久宁。”王浑进曰：“元海长者，浑为君王保明之。且大晋方表信殊俗，怀远以德，如之何以无萌之疑杀人侍子，以示晋德不弘。”帝曰：“浑言是也。”
会豹卒，以元海代为左部帅。太康末，拜北部都尉。明刑法，禁奸邪，轻财好施，推诚接物，五部俊杰无不至者。幽冀名儒，后门秀士，不远千里，亦皆游焉。杨骏辅政，以元海为建威将军、五部大都督，封汉光乡侯。元康末，坐部人叛出塞免官。成都王颖镇鄴，表元海行宁朔将军、监五部军事。
惠帝失驭，寇盗蜂起，元海从祖故北部都尉、左贤王刘宣等窃议曰：“昔我先人与汉约为兄弟，忧泰同之。自汉亡以来，魏晋代兴，我单于虽有虚号，无复尺土之业，自诸王侯，降同编户。今司马氏骨肉相残，四海鼎沸，兴邦复业，此其时矣。左贤王元海姿器绝人，干宇超世。天若不恢崇单于，终不虚生此人也。”于是密共推元海为大单于。乃使其党呼延攸诣鄴，以谋告之。元海请归会葬，颖弗许。乃令攸先归，告宣等招集五部，引会宜阳诸胡，声言应颖，实背之也。
颖为皇太弟，以元海为太弟屯骑校尉。惠帝伐颖，次于荡阴，颖假元海辅国将军、督北城守事。及六军败绩，颖以元海为冠军将军，封卢奴伯。并州刺史东嬴公腾、安北将军王浚，起兵伐颖，元海说颖曰：“今二镇跋扈，众余十万，恐非宿卫及近都士庶所能御之，请为殿下还说五部，以赴国难。”颖曰：“五部之众可保发已不？纵能发之，鲜卑、乌丸劲速如风云，何易可当邪？吾欲奉乘舆还洛阳，避其锋锐，徐传檄天下，以逆顺制之。君意何如？”元海曰：“殿下武皇帝之子，有殊勋于王室，威恩光洽，四海钦风，孰不思为殿下没命投躯者哉，何难发之有乎！王浚竖子，东嬴疏属，岂能与殿下争衡邪！殿下一发鄴宫，示弱于人，洛阳可复至乎？纵达洛阳，威权不复在殿下也。纸檄尺书，谁为人奉之！且东胡之悍