1915年夏天，33歲的蔡鍔，在妓院結識了年方16歲、容貌與彈唱俱佳的小鳳仙。小鳳仙生於杭州一戶沒落的滿族武官人家，十三四歲時，父母雙亡，她被姓曾的人家買去當丫鬟，一年之後，竟被曾家轉賣給了上海的清河坊妓院，淪落風塵。此後，她又輾轉來到了北京，在八大胡同的陝西巷青雲班當妓女，取名小鳳仙，以伴唱賣身。如此不幸的身世經曆，讓小鳳仙過早地領受了人世間的淩辱之苦。
與蔡鍔相處的日子裏，小鳳仙逐漸感覺到蔡鍔是一位文武全才、懷有遠大抱負的人。小鳳仙的不俗氣質，也讓蔡鍔寫下了“自古佳人多穎悟，從來俠女出風塵”的詩句。
據蔡鍔的長子蔡端回憶，其生母潘夫人曾經給他講過：有一次蔡鍔陪家眷去看戲，開場前指著包廂裏一年輕女子對潘夫人說，她就是小鳳仙。從這個細節可以看出，蔡鍔和小鳳仙的交往，從未隱瞞過家裏人，是光明正大的。
在蔡鍔的寓所附近，袁世凱的人一直在密切監視著蔡鍔的行蹤。剛開始，他們發現蔡鍔搬到了雲吉班小鳳仙的妝閣內，再往後，蔡鍔與小鳳仙公開討論起嫁娶之事。在當時，這些都成為北京城裏大小報紙大篇報道的八卦新聞。蔡鍔和小鳳仙的風花雪月，讓袁世凱誤以為蔡鍔並無二心，準備在北京定居了。袁世凱逐漸放鬆了戒備，直到1915年11月11日，蔡鍔在他的眼皮子底下離開了北京，他才恍然驚醒，卻為時已晚。
新中國成立後，小鳳仙曾在沈陽向梅蘭芳回憶當年蔡鍔逃離北京的經過：臨行前，蔡鍔對小鳳仙說：“我要走了，你想辦法，讓我從這裏脫身。”小鳳仙給蔡鍔找了一間北屋，他背向窗，坐在那裏喝酒，故意讓外邊監視的人可以透過玻璃看見。之後，小鳳仙找人假扮蔡鍔仍坐在那裏喝酒，並秘密將真蔡鍔送出雲吉班。就這樣，在監視人員的注視下，小鳳仙成功使用移花接木的方法，順利地將蔡鍔送上南下的火車。
離京後，蔡鍔曾寫了兩篇《呈袁世凱文》，以自己生病為由要求出京休養，袁世凱都給予了批準。從這兩篇呈文和袁世凱的批令來看，蔡鍔離京赴日還是比較從容的。對於此事，袁世凱曾對時任財政總長周學熙說：從蔡鍔臨行時的深謀遠慮來看，“此人之精悍遠在黃興及諸民黨之上，即宋教仁或亦非所能匹”。現在遠走高飛必為心腹大患，並感歎“縱虎出柙”，大有悔意。
蔡鍔出走後，為了對外造成蔡鍔仍是他的人的印象，袁世凱把蔡鍔請假的呈文和自己的批令，一並交給《政治公報》公開刊登。而私下裏，他槍斃了失職的密探，同時派人火速赴天津，試圖抓蔡鍔回京，但蔡鍔已經是一去不複返了。
逃離北京來到天津後，蔡鍔專門去拜訪了一位故人。在這位朋友的兩層小樓裏，他們製訂了一項秘密計劃，而計劃的實施對近代中國產生了巨大影響。
那麼這位故人究竟是誰？蔡鍔又在密謀什麼樣的計劃呢？