而李存勖出身於西突厥沙陀部，本姓朱邪，世為沙陀酋長。祖父朱邪赤心因鎮壓龐勳兵變有功，被唐朝皇帝賜為李姓，編入宗室譜籍。父親李克用，官至河東節度使，封晉王，駐節太原，建立河東割據勢力（晉國）。
當時，梁王朱溫盤踞宣武鎮（治所汴州，在今河南開封），控製中原地區。李克用與朱溫為爭奪中原霸權，進行了二十餘年的梁晉爭霸戰爭。
李存勖是李克用與側妃曹氏所生，自幼便善於騎射，膽略過人，心性豁達，深得父親寵愛。他愛讀《春秋》，略通微言大義，而且精擅音律，可謂文武雙全。
乾寧二年（895年），邠寧節度使王行瑜聯合鳳翔節度使李茂貞、鎮國節度使韓建，攻入長安（治今陝西西安），謀廢唐昭宗。李克用率軍勤王，討平三鎮叛亂。李存勖時年十一歲，也隨軍征戰，並入朝獻捷，受到唐昭宗的誇獎與賞賜。不久，李存勖被授為檢校司空，遙領隰州刺史，後改領汾州、晉州。
天複二年（902年），李克用因太原兩次被梁軍圍困，無力抗衡朱溫，為此憂慮不安。李存勖勸慰道：“物不到極點不會反複，惡不到極點不會消亡。朱溫威逼天子，覬覦帝位，陷害良善，可謂是自取滅亡。我家三代盡忠王室，如今雖因勢窮力屈無法報效，但也無愧於心。父親您應忍耐靜觀，積蓄力量，以待朱溫衰弱之時再圖複興，怎能輕易就灰心喪氣呢。李克用因而釋然。
天祐三年（906年），朱溫遣軍攻打滄州（本屬橫海鎮，時為幽州鎮治下），幽州節度使劉仁恭遣使向李克用求救。李克用惱怒劉仁恭的反複無常，不願發兵援助。李存勖卻道：“如今朱溫已占據天下的九分之七，連魏博、成德等藩鎮也歸附於他，黃河以北能與之對抗的隻剩下我晉國和劉仁恭了。如果我們不救劉仁恭，形勢將會對我們更加不利。而若出兵援助，可使我晉國重振雄風，萬不能因嫌怨而失此良機。”李克用遂遣軍攻取潞州（治今山西長治），迫使朱溫由滄州撤兵。
天祐四年（907年），朱溫篡唐稱帝，建立後梁，史稱梁太祖。他改元開平，定都於汴州。但李克用拒不承認後梁政權，仍沿用唐朝天祐年號，以複興唐朝的名義與後梁相對抗，成為後梁北方最大的威脅。是年五月，朱溫派十萬兵馬圍攻潞州，修築夾寨。李克用命周德威援救潞州。但周德威與梁軍對峙年餘，卻始終不能解除潞州之圍。
天祐五年（908年），李克用病逝。李存勖繼任河東節度使，襲封晉王，時年二十四歲。當時，李克用的養子李存顥、李存實等人自恃手握軍權，又年長於李存勖，對李存勖襲位非常不滿。他們有的稱病不朝，有的見而不拜，甚至慫恿叔父李克寧發動叛亂，意欲謀害李存勖，投降後梁。李存勖沉著應對，首先取得監軍張承業、大將李存璋等人的支持，而後搶先行動，在府中埋伏甲士，擒殺李克寧、李存顥等人，初步穩固了國內政局。
是年四月，李存勖親自率軍援救潞州，於二十九日抵達潞州北麵的黃碾（在今山西長治）。梁軍本以為李存勖年輕繼位，必然不敢出軍，對此毫無防備，也未派出斥候探查。五月初二，李存勖伏兵於三垂岡下，趁著大霧直攻夾寨，出其不意的大破梁軍，徹底解除了潞州之圍。經此一戰，晉國兵威大振。不久，李存勖返回太原，犒賞軍士，而後開始整頓內政。他嚴肅軍紀、撫恤孤寡，任用賢才，懲治貪腐，寬緩刑罰，打擊盜賊，使得晉國民俗大變，百姓歸心。
天祐七年（910年）十一月，朱溫遣軍三千進駐深州、冀州，企圖奪取成德、義武兩鎮。成德節度使王鎔、義武節度使王處直先後遣使向李存勖求援，表示願與晉國結成反梁同盟，共推李存勖為盟主。李存勖力排眾議，毅然發兵相救。他親率晉軍東進，於是年十二月進至距離柏鄉五裏處的野河（今滏陽河支流）北岸，與梁軍隔河對峙。
天祐八年（911年）正月，李存勖命周德威率三百精騎到梁軍營前挑戰，激怒梁將王景仁，將梁軍誘至鄗邑以南的平原曠野地帶。他利用地形優勢，以逸待勞，在梁軍疲憊時率騎兵突擊，大破梁軍，俘獲梁軍將校二百八十五人，斬首二萬級。此戰，梁軍伏屍數十裏，龍驤、神威、神捷等精銳禁軍全軍覆沒，王景仁、韓勍、李思安僅率數十騎連夜逃歸。成德鎮、義武鎮從此徹底倒向晉國。
柏鄉之戰後，李存勖決定暫緩對後梁的攻勢，先奪取河北地區，以消除後顧之憂，首要目標便是囚禁父親劉仁恭而繼任幽州節度使的燕王劉守光。他采用驕兵之計，聯合成德、義武、昭義、振武、天德五鎮，遣使奉冊，共尊劉守光為尚父，以滋長其野心。劉守光卻以為六鎮是畏懼幽州兵威，更是驕狂。他得知尚父無權祭天、改元，不顧幕府諸將反對，於天祐八年（911年）八月在幽州悍然稱帝，國號大燕，史稱桀燕。是年十二月，李存勖命周德威兵出飛狐口（在今河北蔚縣），聯合成德鎮、義武鎮一同征討劉守光。
天祐九年（912年），周德威奪取涿州，進圍幽州。劉守光忙向後梁求救。朱溫親率大軍北上，命楊師厚圍攻棗強，又命賀德倫攻打蓚縣（治今河北景縣）。但梁軍雖攻破棗強，卻在蓚縣被晉將符存審、史建瑭擊敗。朱溫羞憤發病，返回洛陽，不久便被其子朱友珪弑殺。
天祐十年（913年），朱友貞發動政變，誅殺朱友珪，奪取帝位，史稱梁末帝。而晉軍則連奪幽州鎮統轄的順州（治今北京順義）、檀州（治今北京密雲）、武州（治今河北宣化）、平州（治今河北盧龍）、營州（治今遼寧朝陽）等地。是年十一月，李存勖親征燕國，攻破幽州，俘獲劉仁恭（一直被劉守光囚禁）、劉守光父子。他留周德威鎮守幽州。
天祐十一年（914年），李存勖返回太原，處死劉仁恭父子，以祭奠李克用。當時，李存勖南破後梁，北定桀燕，威震天下。王鎔、王處直相繼遣使入晉，共推李存勖為尚書令。存勖依禮三辭，而後接受尚書令之職。他在太原開設霸府，建立行台，以唐朝皇帝的名義承製任命官吏。