李鸿章和洋人打交道是从他到达上海之后便开始的。1862 年 9 月，“常胜军”的第一任头目华尔被太平军打死，引发了由谁来继任的问题。英侵华海军司令何伯向李鸿章推荐了华尔的副手美国人白齐文。李鸿章多方周旋提出条件，“常胜军”属于中国的军队，要由他统一调遣。不久，李鸿章派白齐文去援助南京的湘军，可是白齐文却不听命。他埋怨杨坊催促他启程，就以索要军饷为名到杨坊家抢走了洋银四万两，并痛打了杨坊。李鸿章决定借机整顿常胜军。他将白齐文革职，裁军1500 人，并设立两名头目，一位中国的，一位外国的。这样，戈登就成了新的“常胜军”首领。
戈登和李鸿章最初的合作还不错。可是，由于“苏州杀降”一事，导致戈登对李鸿章极为不满。事情经过是这样的：
在戈登和郜永宽等人私下交易之后，戈登自认有功，要求李鸿章给常胜军发两个月的恩饷，并威胁李鸿章说如果不给，就要辞职。李鸿章回答说他会考虑。然后，戈登去看望苏州城中的郜永宽等人，郜永宽表示对戈登的安排很满意。后来，戈登听说李鸿章只答应给一个月的恩饷时，他就真的开船准备走了。戈登刚刚走出城门，就听到有枪声，他感觉很奇怪。有人告诉他说，李鸿章不允许郜永宽他们保留旧部，在派人鸣枪示威。戈登感觉事情不妙，于是派人去抓李鸿章。可是他没抓到李鸿章，自己反而被淮军扣留。第二天早晨，戈登得知郜永宽等人已被李鸿章杀掉！戈登怒不可遇，他觉得李鸿章不但不给恩饷，还在郜永宽等人的事情上把自己给玩弄了，大英帝国军官的颜面往哪里放？他气急败坏地拿着一只手枪到处寻找李鸿章，说要杀了他。之后，戈登提出要李鸿章辞职，把李鸿章交由北京政府审判，否则，就要率领“常胜军”把淮军已经收回的地方再夺回来，交给太平军。
李鸿章派出“常胜军”的军医即后来帮助李鸿章兴办洋务的马格里出面调节。英国也派人做李鸿章的工作，要求李鸿章给戈登写道歉书，被李鸿章拒绝。后来李鸿章拨给“常胜军”7 万两军饷，又派出朝廷新任命的海关总税务司英国人赫德前去调停。赫德的前任、英国人李泰国因为和李鸿章作对，没有落得好下场。戈登听了赫德的话，想想自己离开“常胜军”之后也是没有更好的着落。于是，他又回到了“常胜军”。
此后，戈登和李鸿章的关系一直不错。戈登还多次对人夸赞李鸿章，说他是个有头脑的军事家。1863年，淮军攻打常州。常州将领吸取苏州的教训，拼死守城，不肯投降。李鸿章请来戈登协助，戈登用大炮轰开了城门，协助淮军收复常州。由于戈登事先没有征求英国官方的同意，英国感到难以控制“常胜军”，英国驻军司令伯郎向英国政府提出解散“常胜军”。
“常胜军”本来就是中国人的雇佣军，英国政府没有权利解散。英国政府要求：在“常胜军”中服役的英国现役军官全部离开“常胜军”，并撤销戈登的假期和一些特权。戈登十分不满，他找到李鸿章说，现役军官都退出“常胜军”，与其这样，还不如把“常胜军”解散，但是需要遣散费 16 万元。李鸿章早就有解散“常胜军”的意思，只是一直苦于没有机会。李鸿章觉得时机已到，马上表示同意。
驻上海的英国总领事巴夏礼提出解散“常胜军”需要他和英国驻华公使协同办理，赫德也提出“常胜军”不可解散。戈登又犹豫不决。李鸿章派出丁日昌劝告戈登要吸取白齐文被解职的教训，说“常胜军”现在声名不好，你留在这里对你的名誉也有影响，你要为自己考虑。李鸿章迅速筹集遣散费 19 万两（超出 3 万两），全部交给戈登。只留下炮兵 600 人和洋枪队 300 人，外国教官 11 人，其余全部解散。戈登拿着钱，还得了清政府颁发的提督荣誉军衔，风风光光地回英国去了。事后，曾国藩赞叹李鸿章居然能够驾驭外国人。这也许是李鸿章的“痞子手段”的灵活运用吧。