1898年9月，戊戌變法失敗，梁啟超亡命日本。蔡鍔也因時務學堂被解散，求學兩湖書院遭拒絕，幾經周折，於1899年6月考入上海南洋公學。7月，接梁啟超來函相召，蔡鍔偕唐才質、範源濂等人東渡日本，進入由梁啟超主持的東京高等大同學校學習，研究政治哲學。
學校所用教材多采歐美自由平等、天賦人權之說，使蔡鍔耳目為之一新。而且，梁啟超與唐才常過從甚密。受唐才常的影響，蔡鍔加入“自立會”，並於1900年7月回國參加自立軍起義。不旋踵起義失敗，蔡鍔雖幸免於難，但受刺激很大，為此事，他曾賦詩十首，其中有雲：“流血救民吾輩事，千秋肝膽自輪菌。”並將原名艮寅改為鍔，意在砥礪鋒鍔重新做起，決心學習軍事，以拯國難。據1996年嶽麓書社出版《憶蔡鍔》，這時，蔡鍔以學習陸軍為念，屢請於梁啟超，並堅定表示：“隻須先生為我想方法得學陸軍，將來不做一個有名之軍人，不算先生之門生。”梁啟超利用他與日本政界的密切聯係，幫助蔡鍔實現了學習陸軍的願望。蔡鍔先後畢業於日本東京成城學校和陸軍士官學校。
留日期間，蔡鍔曾投稿於梁啟超主辦的《清議報》，嗣又在梁主辦的《新民叢報》上發表文章，而《軍國民篇》就是他刊登於該報的一篇代表作。在此文中，蔡鍔沉痛指出：“居今日而不以軍國民主義普及四萬萬，則中國其真亡矣。”提出以軍國民主義灌輸於國人頭腦，以培養“國民新靈魂”，來實現軍事救國的目的。這種從軍事入手進行改革的軍事改良主義，與梁啟超的改良思想是一脈相承的。
由於西學的啟迪，加以梁啟超於1900年前後曾密謀與革命派合作，極力鼓吹所謂“破壞”，甚至認為“破壞之藥”是救國的“第一要件”，“第一美德”，蔡鍔受其影響，開始結交一批革命誌士，並參與組織團體，從事反清革命活動。雲南光複後，蔡鍔被推為軍政府都督，建立了具有資產階級民主革命性質的都督府，並進行了若幹帶有民主主義色彩的改革。
清帝退位之後，蔡鍔認為“破壞”已基本告一段落，下一步主要任務是團結各種政治力量，共圖建設。1912年6月5日，蔡鍔致電袁世凱及各省都督，敦請恩師梁啟超回國，電文稱：“鍔追隨先生有年，覺其德行之堅潔，學術之淵博，持義之穩健，愛國之真摯，環顧海內，實惟先生之一人。”同年10月，梁啟超結束流亡生涯，體麵回國，這與蔡鍔不無關係。梁返國後，在“開明專製”思想的指導下，極力鼓吹“國權主義”，希望通過袁世凱建立強有力政府，推動國家建設。蔡鍔亦主張建立強有力政府，與梁產生思想共鳴，他認為：“特以民權恒視國權為伸縮，必國權鞏固而後民權有發展之期。總統當國家行政之中樞，負人民付托之重任，使因少數人之黨見，減削其行使政策之權，恐一事不能為，必致陷國家於不振之地”，這與梁的“國權主義”如出一轍。
在民國初期激烈的黨爭中，蔡鍔始終反對各派利用政黨作為爭權奪利的工具，並主張“軍人不黨主義”，退出了統一共和黨。但1913年5月進步黨成立之後，他秉承梁啟超的旨意，加入進步黨。蔡鍔自言：
“今承吾師指命為名譽理事，義又不得辭，惟有勉從諸公之後，為默示之承認而已。”1913年7月12日，李烈鈞宣布江西獨立，“二次革命”爆發。蔡鍔同梁啟超一樣，視革命黨為“洪水猛獸”，反對“二次革命”。他認為“積年癰毒，趁此一決，未始非福。第恐戰事延長，蔓延太廣，此後殊難收拾”，“惟懇分飭皖、寧嚴防分竄，一麵添重兵馳赴戰地，分頭截剿，早日撲滅，以免星火燎原。”蔡鍔在“二次革命”中無疑是擁袁的，因為他既受梁之影響，也尚未識破袁世凱的野心。
1915年8月，袁世凱複辟帝製的活動公開化，梁啟超和蔡鍔一反過去擁袁的政治立場，轉而籌備反袁。蔡鍔與梁啟超在反袁護國戰爭的組織發動及戰爭的進程中確實起到了重要作用。8月14日，為袁複辟帝製搖旗呐喊的“籌安會”成立，15日，蔡鍔便趕赴天津，與梁秘密策劃反袁。蔡鍔當即表示：“我們明知力量有限，未必抗得他過。但為四萬萬人爭人格起見，非拚著命去幹一回不可。”（梁啟超：《文集之三十九》，《飲冰室合集》，中華書局1936年）他們共同商定，發揮各人特長，分別從文、武兩條戰線反袁。由蔡鍔親自回雲南發動武裝討袁，梁啟超則大造反袁輿論。22日，梁啟超拒絕袁世凱的收買，公開發表《異哉，所謂國體問題者》，明確表示反對帝製複辟。梁利用他在思想輿論界的顯赫地位，聯絡各派頭麵人物反袁，是護國運動的一麵旗幟。
蔡鍔每周都赴天津與梁共商大計，並召集戴戡等重要人物入京，部署一切。蔡鍔利用他與各派政治力量之間所保持的良好關係，聯絡西南實力派，並與在美國的黃興取得聯係，秘密實施與梁商定的各項反袁計劃。1915年11月11日，蔡鍔設計秘密出京，曆盡艱險，於12月19日繞道日本，抵達雲南昆明，12月25日發動了著名的討袁護國之役。
在戰爭進行當中，二人同舟共濟，互相支持。蔡鍔在軍事上領兵鏖戰，梁啟超在思想戰線等方麵密切配合，共同推進反袁鬥爭事業。
梁啟超一方麵向蔡鍔指陳革命方略，策劃與指導軍事行動，誠如蔡鍔所雲：“鍔在軍中凡得先生八書，每書動二三千言，指陳方略極詳。”另一方麵，梁又利用他的特殊地位，擴大反袁聯合陣線，為雲南護國軍掃清障礙。在蔡鍔最困難之時，梁策動桂督陸榮廷獨立，促進了全國反袁形勢的根本性轉變。後來，梁冒著生命危險南下廣東，策動龍濟光獨立，並使龍濟光最終宣布獨立，從而加速了袁世凱的失敗。蔡鍔認為：“先生亦間關入兩粵，當鍔極困厄之際，突起而拯救之，大局賴是以定。”高度評價了梁啟超在護國運動中不可磨滅的曆史貢獻。而梁啟超在以後的歲月中一直以有這樣一位反袁的學生為榮。蔡鍔逝世六年後，即1922年，梁啟超應湖南省長趙恒惕之邀在長沙作題為《奮鬥的湖南人》的演講，重點舉了蔡鍔反袁護國之例。演講中說：
民國成立，袁世凱稱帝，自以為布置周密，預料必可成功。那時蔡鬆坡離居在京，算已入了袁的樊籠，但他千辛萬苦設法逃去袁的勢力範圍，突然在滇起義，以很單薄的兵力出四川，袁傾全國之力同他相持。結果居然摧倒袁氏，使他活活地氣死。然而鬆坡也因為勞頓過度，得了吐血症，後來死在日本的醫院裏。那時出力的不止蔡鬆坡，同事的湖南人也很多。（湖南《大公報》，1922年9月3日，第七版）