東郡周邊除了瓦崗寨這個最大的勢力之外還有很多小股盜匪，李密開始投奔他們的時候遭到了如前一樣的待遇，沒有人把他當回事。其實這也是必然的，這些揭竿而起的盜匪絕大多數都是文盲，既無遠大的目標也無鮮明的革命綱領，而李密這樣軍師型的前貴族以謀略文化見長，自然與這些粗漢格格不入。不過這次李密沒有放棄，而是時時刻刻向這些人陳說怎麼逐鹿中原、奪取天下。一開始這幫人都不聽他的勸告，該怎麼還怎麼幹。但是形勢比人強，這天下真的如李密所說的一天天糜爛了，於是這些盜匪才不敢小看李密。另外當時一個流傳非常廣的預言也幫了李密的大忙，那就是中國曆史當中幾大不可解的預言謎團中最著名的一個——“楊氏將滅，李氏將興”。有了這個預言，再加上李密最開始的身份就是跟隨楊玄感的義軍頭目，又屢次遭到圍捕卻安然無恙。古代的人大多迷信，這些林林總總的事情使李密被套上了一圈神秘的光環。於是，這些盜匪拜李密為主，成為李密起義的基本力量。評書中提到的“神箭無敵”的勇三郎王伯當便在此時成了李密最忠心的部下。
收服了這些小股盜匪之後，李密把眼光投向了他所在區域最大的反抗勢力瓦崗寨，並通過王伯當與翟讓牽上了線。一開始翟讓也瞧不起李密，隨便給了李密一個任務，讓他說服周邊小股勢力歸降。不過李密現在已經今非昔比，他將被他折服的幾股小勢力整合以後算得上是小有家底，因此很快圓滿完成了任務。翟讓這才對李密刮目相看，轉而將其作為一個可以商討大事的頭領來對待。
李密在正式被瓦崗寨接納之後又將之前對王伯當等人幹過的事一再重複，對翟讓開始了猛烈的勸說，揭竿而起打倒皇帝，但翟讓對此並不感冒，還是堅持打家劫舍，隻圖個逍遙快活，讓李密白費了一番唇舌。但李密沒有放棄，他一邊招收有能力的豪傑為其所用，一邊收買翟讓的心腹向其鼓吹，讓翟讓越發信任李密。經過多番謀劃，李密終於成為翟讓的最倚重的人，其說話的分量也大大增強。這次李密再也沒有像一開始那樣企圖一蹴而就，用一些大而無當的話忽悠翟讓，而是提出了一個在戰略上是高瞻遠矚的謀劃，那就是攻打滎陽。
滎陽素有“東都襟帶，三秦咽喉”之稱，曆來為兵家必爭之地。且其北的鴻溝滎口為隋代水運機樞，四通八達，經濟繁榮，自漢以來即為“天下名都”。對於瓦崗軍來說，滎陽除了地理位置非常重要之外，更重要的是能解決他們的吃飯問題。由於隋煬帝的暴政，農民流離失所，大量的田地荒蕪，直接導致了糧荒。而對瓦崗軍來說，沒有糧食就養不起太多的精兵，要真正地爭霸天下就必須走一條可持續發展的道路。隋朝在隋文帝時期開始建立了很多大糧倉，這些糧倉裏麵儲存的糧食號稱可以供政府五六十年的用度。而滎陽西南就有號稱“天下第一糧倉”的洛口倉，隻要打下洛口倉，瓦崗軍便有了爭霸天下的資本。
經受不住李密的勸說，翟讓終於決定搏一把，於是瓦崗軍兵發滎陽並於大業十二年（616）十月攻破金堤關（今河南滎陽東北），拿下了滎陽諸縣。這樣一來又惹出了身為討捕大使的張須陀，瓦崗軍此前吃了他不少的虧，翟讓的勇氣也僅僅維持至見到張須陀的那一刻。就這樣，瓦崗軍對張須陀的畏懼終於壓過了對城內物資財寶的渴望，隻略作攻擊便立刻下令撤退，而張須陀自然不會放棄如此大好機會，窮追十餘裏，他卻不知道這次翟讓的背後還有一個李密，還是按照以前交手的經驗來，最終付出了生命的代價。
就在翟讓領兵前行，李密卻率領了本部千餘人埋伏在大海寺北林間。等張須陀追擊十餘裏，隊形不整、人困馬乏之時伏兵突發，將張須陀所在的中軍截斷，使隋軍混亂。此時前麵的瓦崗軍又返身殺回，前後夾攻之下，張須陀兵敗。張須陀人生的最後一刻非常感人。李密伏兵初發，張須陀在第一時間殺出了包圍圈，可他的左右部下卻沒能突圍出來。張須陀又殺入包圍圈進行營救，進出數次卻回天乏術，在軍隊最終潰敗後，下馬英勇地戰鬥至死，享年五十二。他戰死後部下“盡夜號哭，數日不止”。可見其得軍心之處。他的殘部後來撤退至虎牢關，由新任河南道討捕大使裴仁基統屬。
張須陀的戰死對朝廷在河南的統治打擊非常之巨大，據稱“河南郡縣為之喪氣”。這位可敬的救火隊員的離去仿佛抽掉了隋朝的最後一根梁柱，整個大廈的倒塌不過是時間問題了。
大海寺戰役讓李密玩了一招漂亮的斬首行動，但是戰後的隋殘軍依然擁有較強的實力，張須陀手下大將如秦瓊、羅士信都安然無恙，就連張須陀自己若非顧及下屬性命，也可走脫，由此可見農民組成的瓦崗軍在麵對全副武裝的朝廷正規野戰軍的時候依然非常虛弱，因此翟讓打完這一仗之後便打起了退堂鼓。他在滎陽搜刮了一番，收獲不少，便想回到瓦崗寨做山大王去。不過在撤回之前，翟讓正式承認了李密在瓦崗寨的半獨立身份，同意李密開府建牙，成立了薄山公營。這樣一來，與其說李密是瓦崗寨的一員還不如說他是翟讓的合夥人，隻不過此時翟讓所占的“股份”還是遠大於李密。