李鴻章和洋人打交道是從他到達上海之後便開始的。一八六二年九月，「常勝軍」的第一任頭目華爾被太平軍打死，引發了由誰來繼任的問題。英侵華海軍司令何伯向李鴻章推薦了華爾的副手美國人白齊文。李鴻章多方周旋提出條件，「常勝軍」屬於中國的軍隊，要由他統一調遣。不久，李鴻章派白齊文去援助南京的湘軍，可是白齊文卻不聽命。
白齊文不敢和李鴻章直接作對，便拿在松江的道台楊坊出氣。他跑到楊坊家裡，將他毒打一頓，同時將楊府中搜到的四萬塊洋銀搶劫一空。白齊文幹了壞事自覺理虧，逃到英國軍隊中隱匿起來。曾國藩對李鴻章援軍未至一事倒不怎麼在意，因為他要求增援只是想招回程學啟部。至於「常勝軍」，曾國藩說過這麼一段話：「『常勝軍』不來南京沒什麼不好，來了倒沒有什麼好處！」李鴻章卻對白齊文不聽調遣、毆打朝廷命官且入室搶劫之事不能容忍。當然，這種棘手之事老奸巨猾的李鴻章不會親自處理，他令吳煦限期將白氏捉拿歸案，要求「常勝軍」轉由中國官員接管，外人不得干涉。英國軍隊見李鴻章真動了怒，覺得不便為一個白齊文破壞中英兩國關係，決定交出白齊文。然而，英國駐華水師司令迪佛立與白齊文私交甚篤，強硬堅持不肯交出白齊文。李鴻章決心以此為突破口，改組「常勝軍」。李鴻章改組「常勝軍」主要有兩個目的，一是削減「常勝軍」的經費，將錢省下來發展淮軍；二是收回「常勝軍」兵權。無理也硬三分的英國人當然不會同意李鴻章的改組方案。英國政府任命戈登為新任「常勝軍」統領以取代白齊文。
戈登的到來使李鴻章心中著實「咯噔」了一下。他意識到英國絕不會輕易放棄「常勝軍」領導權的險惡用心，不能與其硬碰硬。李鴻章遂託人調查戈登的底細，得知戈登出身於軍官世家，對軍事地形學和步炮聯合作戰有精深的研究，性格弱點是愛慕虛榮、貪財。戈登一到中國，便受到李鴻章的熱烈歡迎。
戈登來中國之前聽說李鴻章是一個鐵腕人物，將前任嚇得躲在軍艦裡不敢出來，早已做好應對的心理準備。但見到李鴻章後，戈登改變了看法，他在給英國政府發去的公函中極力稱讚李鴻章，稱其是中國最傑出的軍事家和政治家，為人正直、思想先進，熱心發展西方軍工業，我們英國政府不但不應與之作對，而且應全力幫助支持。
戈登和李鴻章最初的合作還不錯。可是，由於「蘇州殺降」一事，導致戈登對李鴻章極為不滿。事情經過是這樣的：
在戈登和郜永寬等人私下交易之後，戈登自認有功，要求李鴻章給常勝軍發兩個月的恩餉，並威脅李鴻章說如果不給，就要辭職。李鴻章回答說他會考慮。然後，戈登去看望蘇州城中的郜永寬等人，郜永寬表示對戈登的安排很滿意。後來，戈登聽說李鴻章只答應給一個月的恩餉時，他就真的開船準備走了。戈登剛剛走出城門，就聽到有槍聲，他感覺很奇怪。有人告訴他說，李鴻章不允許郜永寬他們保留舊部，在派人鳴槍示威。戈登感覺事情不妙，於是派人去抓李鴻章。可是他沒抓到李鴻章，自己反而被淮軍扣留。第二天早晨，戈登得知郜永寬等人已被李鴻章殺掉！戈登怒不可遏，他覺得李鴻章不但不給恩餉，還在郜永寬等人的事情上把自己給玩弄了，大英帝國軍官的顏面往哪裡放？他氣急敗壞地拿著一隻手槍到處尋找李鴻章，說要殺了他。之後，戈登提出要李鴻章辭職，把李鴻章交由北京政府審判，否則，就要率領「常勝軍」把淮軍已經收回的地方再奪回來，交給太平軍。
李鴻章派出「常勝軍」的軍醫即後來幫助李鴻章興辦洋務的馬格里出面調解。英國也派人做李鴻章的工作，要求李鴻章給戈登寫道歉書，被李鴻章拒絕。後來李鴻章撥給「常勝軍」七萬兩軍餉，又派出朝廷新任命的海關總稅務司英國人赫德前去調停。赫德的前任、英國人李泰國因為和李鴻章作對，沒有落得好下場。戈登聽了赫德的話，想想自己離開「常勝軍」之後也是沒有更好的著落。於是，他又回到了「常勝軍」。
此後，戈登和李鴻章的關係一直不錯。戈登還多次對人誇讚李鴻章，說他是個有頭腦的軍事家。一八六三年，淮軍攻打常州。常州將領吸取蘇州的教訓，拚死守城，不肯投降。李鴻章請來戈登協助，戈登用大炮轟開了城門，協助淮軍收復常州。由於戈登事先沒有徵求英國官方的同意，英國感到難以控制「常勝軍」，英國駐軍司令伯郎向英國政府提出解散「常勝軍」。上海防務由駐滬英軍承擔。
李鴻章雖有思想準備，卻萬萬沒料到英國會同意解散「常勝軍」。機不可失，李鴻章當即宣佈解散「常勝軍」。李鴻章一宣佈此消息，英國人倒不滿起來。駐華領事巴夏禮發出照會，稱解散「常勝軍」一事只有英國公使方可辦理，李鴻章無權作出決定。李鴻章深知英國人的脾性，如果錯過這次機會，想徹底擺脫「常勝軍」就困難了。戈登又猶豫不決。李鴻章知道戈登一向好名，便以躲在軍艦中的白齊文為例，曉以利害，告誡戈登，人生在世名聲最為重要，不要為別人的利益把自己給毀了。李鴻章派出丁日昌勸告戈登要吸取白齊文被解職的教訓，說「常勝軍」現在名聲不好，你留在這裡對你的名譽也有影響，你要為自己考慮。李鴻章迅速籌集遣散費十九萬兩（超出三萬兩），全部交給戈登。只留下炮兵六百人和洋槍隊三百人，外國教官十一人，其餘全部解散。戈登拿著錢，還得了清政府頒發的提督榮譽軍銜，風風光光地回英國去了。事後，曾國藩讚嘆李鴻章居然能夠駕馭外國人。