1859年1月，怀着悲凉心情自称“书剑飘零旧酒徒”的李鸿章，终于受到命运之神的惠顾，从一个潦倒失意客一跃而成为湘系首脑曾国藩的幕宾，从此他的宦海生涯又翻开了新的一页。
李鸿章无家可归，只好收拾简单的行囊携带老婆孩子出逃。他辗转来到南昌看望母亲，在哥哥的帮助下，他见到了在建昌的曾国藩。当时曾国藩的局面也不好，正面临三河惨败的情势。虽说湘军在曾国藩的带领下是兵多力壮，一派朝廷之师的威武气象，但湘军旗下真正可用的人才并不多。曾国藩迫切需要一个得力的助手，一个有才华、善通变，能够处理具体事务的干将。而此时，在李瀚章的安排下，曾国藩惊奇地发现，端坐他面前的李鸿章言谈举止卓越超群。他那评判政事的尖锐深刻，那军旅生涯磨砺出的求真务实，那敢于面对失败的勇气，那追求上进施展才华的抱负，都让曾国藩欣赏有加。曾国藩知道，现在的李鸿章，已经不再是京城翰苑中的那个文弱书生，他的身上既增添了几分成熟，又激荡着年轻人的豪气，同时也有渴望干一番大事业的雄心壮志。这次会面之后，曾国藩决定把李鸿章留在身边。于是，李鸿章成为曾国藩的幕僚，并从此开始了他们之间长达数十年的师生之情。
1853年，曾国藩以在籍侍郎的身份，受命帮办湖南团练事宜，他看出“兵伍不精”是清王朝的大患之一，决心独树一帜，改弦更张，编练一支新式武装，以挽救清朝统治。1854年2月，他编成并督率湘军水陆两军，沿湘江北上抗拒太平军。湘军有别于清朝常备军，它是汉族地主武装，“以招募易行伍，尽废官兵，使儒生领农民，各自成营”。曾国藩“在京官时，以程朱为依归，至出而办理团练军务，又变而为申韩。”他采取传统的“以上制下”的战略方针，先清两湖，稳定后方，继而把军锋指向江西和安徽。1858年七八月间，曾国藩先后奉命驰赴浙、闽，进击分裂出走、放弃江西根据地、盘旋浙闽的石达开部太平军。10月，他率部到达建昌，未及入闽，石达开部即由闽入赣，转进湖南，锋锐大挫。是时江南军情渐松，而江北却风云突变。面对江南、江北大营进逼天京、湘军围攻安庆、三河、威逼庐州的严峻形势，陈玉成、李秀成两支主力太平军联合作战，首先摧毁江北大营，解除天京北面威胁，继而在安徽三河全歼李续宾所部湘军精锐六千余人，击毙李续宾和曾国藩胞弟曾国华以及文武官员四百多人。包围安庆的湘军，见势不妙，慌忙逃跑，安庆之围不战而解。曾国藩因“江北军情变幻”而惊恐万分，哀嚎“呜呼恸哉！”12月奉命移师援皖。
在这种形势下，李鸿章赶到建昌拜访了曾国藩。李瀚章是曾国藩与李鸿章结合牵线搭桥的人，李瀚章于1849年以拔贡朝考出曾氏门下，1853年署湖南善化知县，当时在衡阳带兵的曾国藩檄调来营，襄办粮台，遇有战阵，也督队指挥。曾国藩称赞他“内方正而外圆通，办事结实周详，甚属得力。”1857年1月，湘军粮台裁撤，归并江西省局，瀚章回籍为其父守制，安徽巡抚福济奏留办理团防捐务。1858年，曾国藩檄调瀚章赴江西总理粮台报销，瀚章遂奉母同住。曾国藩十分器重瀚章，而瀚章也把曾国藩倚为靠山。瀚章既经常向曾国藩通报鸿章在皖情况，有时甚至将其弟家书转呈曾国藩过目；又时时向鸿章介绍曾国藩的宦海浮沉和吹捧其道德学问。瀚章在其弟与曾国藩之间起着沟通情感、增进了解的作用。时值鸿章到南昌看望老母，曾国藩便乘机通过瀚章邀请鸿章前来会晤。1858年12月，曾国藩函告友人说：“筱泉家被贼焚劫，挈眷至南昌，日内亦即来营，少荃亦约来此一叙。”曾国藩与李鸿章早就结下了师生之谊，曾国藩称誉弟子为“伟器”，李鸿章敬佩其师如“神圣”。他俩有相似的追求：扑灭太平天国烈火、维护清朝统治以期封侯荫子、光宗耀祖；又有相互利用之必要，曾国藩希望借助李鸿章之才以成“大业”，李鸿章企图依靠曾国藩援引以立功名。
对李鸿章的才识，曾国藩早有所知，但认为他性情不稳，妄自尊大，所以故意不见他。一个多月后，李鸿章又托人说情，曾国藩说道：李鸿章也是翰林，志大才高，我这里局面窄狭、只是一条浅沟，容不下他这条大船呀，他何不回京供职？经反复说情，李鸿章终在1859年1月入曾国藩幕，成为曾的幕宾。其实，曾国藩并非不想要他，只是想打一打他的傲气，让他更加内敛沉稳。
在曾国藩幕，李鸿章办理行文、批阅公文，起草书牍、奏章。曾国藩最负盛名的参折《参翁同书片》，即出自李鸿章之手。任安徽巡抚的翁同书是咸丰皇帝和恭亲王的老师，历任工部、户部尚书翁心存的长子，其弟即大名鼎鼎的翁同龢。这道参折指责翁同书举措不当、守城不力、弃城而逃，应予严惩。以翁家的权势，要将其扳倒谈何容易，所以曾国藩极其重视，要文案房多拟几份草稿备选。在好几份草稿中，他选中李鸿章稿。如此重要之折，却只区区不到六百字，可谓字字千钧，句句见血。此折历数翁同书忠奸不辨、误用歹人、措置失当、贪生怕死、连失两城的罪状，然后指出翁的几道奏折的自相矛盾之处，反驳他的种种自辩，令其无继续辩解的任何余地。此折最后写道：翁同书有如此行为“岂宜逍遥法外？应请旨即将翁同书革职拿问，敕下王大臣九卿会同刑部议罪，以肃军纪而昭炯戒。臣职分所在，例应纠参，不敢因翁同书之门第鼎盛瞻顾迁就”。一句“不敢因翁同书之门第鼎盛瞻顾迁就”，即将朝廷因翁同书之“门第鼎盛”本想“瞻顾迁就”从轻发落的“后路”封死，委实老辣。朝廷只得并不情愿地按规定将翁同书判“拟斩监候”。所以曾国藩称赞说：“少荃天资于公牍最相近，所拟奏咨函批，皆有大过人处，将来建树非凡，或竟青出于蓝，亦未可知。”而李鸿章也向人表示自己从前也辅佐过其他将帅，但“芒无指归”，入曾幕才“如识南针，获益匪浅”。
曾国藩生活极有规律，每天很早就起床查营，然后在黎明时分与幕僚共进早餐，或谈一天工作安排或随意谈天说地。初到曾国藩幕时，比较懒散的李鸿章很不适应这种规律、刻板的生活，深以为苦。一天早晨，他以头痛为名想多睡一会儿，但曾国藩知道他是装病多睡，所以几次派人请李鸿章起来一起吃饭，最后告诉李鸿章必须所有幕僚全都到齐才开饭，李鸿章匆忙披衣“踉跄前往”。曾国藩吃饭时一言不发，饭后严肃地教训他说：“少荃，既入我幕，我有言相告，此处所尚，唯一‘诚’字而已。”说罢生气地拂袖而去，李鸿章“为之悚然”。曾国藩素知李鸿章“才气不羁”，故对他要求格外严格，尽力雕琢，陶冶其性情，培养其道德。许多年后，李鸿章对人回忆说：“在营中时，我老师总要等我辈大家同时吃饭；饭罢后，即围坐谈论，证经论史，娓娓不倦，都是于学问经济有益实用的话。吃一顿饭，胜过上一回课。”
李鸿章入幕不及一旬，曾国藩就决定请他主持编练皖北马队，附于湘军。编练马队之举，发轫于左宗棠的提议。左宗棠（字季高）是湖南湘阴人，举人出身，初入湖南巡抚骆秉璋幕，后来成为湘军首领之一。曾国藩就左氏提议同胡林翼协商。胡林翼［字贶（kuàng）生，号润芝，道光进士］时任湖北巡抚，为湘军二号首领。胡氏支持编练马队，曾国藩随即上疏清政府，慷慨陈词。曾国藩所以力主编练皖北马队，是鉴于太平军和捻军的骑兵“多而且悍”，湘军陆军如无马队配合，难以制胜。他通报左宗棠：“阁下去年嘱弟留心马队，弟以调察哈尔之马练淮南之勇人奏。”他原拟调察哈尔马三千匹，令李鸿章招募亳州一带“善马之勇”千人。清政府对曾国藩编练马队持肯定的态度，但又下令“斟酌采买”马匹。根据朝廷的命令，曾国藩修改了募勇计划，决定先招五百，试行操练，如其可用，再行续招三千。李鸿章虽然承认编练马队确系当务之急，但却深感事体重大，缺少经验，胜败难卜，考虑再三，未敢轻许。李鸿章专程前往南昌与哥哥相商。李瀚章赞成其弟意见，致函曾国藩，代为辞谢。曾国藩坚持既定方针，写信劝勉李氏兄弟“不必遽以往事之难为虑”。话已至此，李鸿章只得应命，派“专人至淮上招募马勇”。然而当时两淮地区太平军和捻军协同作战，声势较壮，清军处于被动挨打的地位。动荡的局势，人心的向背，迫使招勇之人空手而归。这样，曾国藩建立马队的计划就流产了。
6月，早已移驻抚州的曾国藩，鉴于太平军猛攻景德镇，担心湘军张运兰部不支，急派曾国荃率部往授，并命李鸿章同往。曾国荃（字沅浦）是曾国藩胞弟，所部为曾国藩嫡系。李鸿章心高气盛，希望独统一军，不愿寄人篱下，心情郁郁，有意他去。曾国藩赏识李鸿章之才而不满其虚骄之气，于是一面借用上方宝剑阻其去路，疏留说：李鸿章“久历戎行，文武兼资，堪以留营襄办”；一面对其晓之以理，诱之以利，说“阁下闳才远志，自是匡济令器”，“倘为四方诸侯按图求索，不南之粤，则东之吴，北之齐豫耳。”李鸿章既不敢抗旨，又感戴其师“荐援”之恩，因而决计前往。
就在这个时候，湖广总督官文根据胡林翼之请而提出的命曾国藩入川防堵石达开部太平军挺进四川的建议被清政府批准了。原本，胡林翼是打算借此为曾国藩谋取川督一职，并确保湖北饷源。不料清政府只令曾氏援川，却不肯授予地方实权。曾国藩自然不愿前往，复奏“兵力太单，难以入蜀，且景镇未克，不可这行抽动”。李鸿章支持曾国藩，函请督办皖南军务张芾奏留曾国藩守赣。3月，由于清政府催促，曾国藩只得带领李鸿章等幕僚拟经鄂入川，行至武穴，又接到官文关于“已奏请会剿皖贼”的通报。原来，胡林翼鉴于曾国藩没有捞到川督一职和石达开军锋业已南指，“蜀中无事”，便说通官文奏准曾氏暂缓入川，全力图皖。9月，曾、李先至黄州会晤胡林翼，后抵武昌晋见官文，商讨行止，决定四路进兵安徽的计划，而其中心目标则是夺取安庆。曾国藩负责从宿松、石牌进取安庆一路。11月，李鸿章奉旨授福建延建邵遗缺道。曾国藩看到李鸿章“新放福建道，无缺可补，进退颇难自决”，便以“赞襄需人”为由，奏准带着他自黄州东下援皖，驻军安徽宿松，与屯军太湖、潜山的陈玉成部太平军相峙。
太平天国“上下夹攻，南北合击”的战略决策让清政府头疼不已。1860年初，清政府根据当前战事，命令江南大营和湘军分别围困天京和“进攻安庆，分捣桐城”。太平军则采取了先救天京、后保安庆的方针。是年5月，李秀成、陈玉成联军一举击溃江南大营，随即挥军东指，挺进苏杭。江南北大营本来是咸丰与曾国藩矛盾的产物。咸丰帝的如意算盘是：既要依靠曾国藩对抗太平军，又不肯给他以军政实权。咸丰的计划是湘军出力，江南北大营收功。江南北大营的相继覆灭，使咸丰的幻想彻底落空。咸丰不得不全力依靠曾国藩来支撑危局，于6月初给他兵部尚书衔、署理两江总督的军政实权。8月实授两江总督。此间，曾国藩曾奏保李鸿章为两淮盐运使，黄翼升为淮扬镇总兵，筹办淮扬水师。对于曾国藩的奏请，清政府并没有全部恩准，只任命黄翼升为淮扬镇总兵，没有授予李鸿章两淮盐运使一职。李鸿章吃了一记闷棍，抑郁寡欢，暗自嗟叹，只得继续留在曾氏幕中。
