1904年冬，蔡锷乘坐的邮轮开进了上海的黄浦江，上岸后，他立即与在上海的革命团体取得了联系，加入杨笃生、章士钊等人发起的“爱国协会”中去，并与黄兴等革命党人相互联络，待机策动起义。第二年春天，他回湖南省亲。闲暇之余，常登临岳麓之巅，面对湘江流水，赋诗明志。他的《登岳麓山》就抒发了精诚爱国的宏伟抱负：“苍苍云树直参天，万水千山拜眼前。环顾中原谁是主？从容骑马上峰巅。”这首诗表明了这位青年爱国志士为了祖国安危、民族命运立志横刀跃马，搏击在时代漩涡的峰巅的决心。
蔡锷回国前后，正处各省掀起编练新军、创办军事学堂的热潮之际，急需懂得近代军事知识的人才。因此蔡锷刚一踏上国土，各省的聘书便纷至沓来。江西巡抚夏时首先聘请他担任江西续备左军随营学堂监督，负责培养当地新式军事人才。1905年初，湖南巡抚端方为了罗致人才编新军，聘请蔡锷任湖南教练处帮办，兼武备、兵目两学堂教官。当时的蔡锷，已经放弃了他老师梁启超的改良主张，积极赞成排除满清的革命。8月，广西巡抚李经羲又奏调蔡锷为广西新军总参谋官和总教习官，兼随营学堂总理官。蔡锷见李经羲对自己如此器重又如此诚恳，于是带领自己的学生雷飙等赴广西任职。到广西不久，又相继兼任新练常备军总教练官、巡抚部院总参谋官，成为广西新军建设的核心人物。
广西地处南疆，防务重要，亟待建设，但广西又是一个财政支绌、人际关系复杂的省份。在这样的形势下，要在军事上作出重大的成效，不是一件容易的事。蔡锷到广西后，凭借自己的声名和才干，在开始阶段是一帆风顺的，他带去的学生也成为他左右的军事骨干，担任了学堂区队长或教官。然而，当蔡锷在广西军界声名鹊起之后，种种矛盾也就接踵而来，许多人冷眼旁观，蔡锷为此发出“孤掌难鸣”的叹息。
1906年秋，清政府在河南举行规模盛大的新军会操，蔡锷奉令前去观操，并被派为中央评判官。这时，他本想借机辞去在广西的各职，但新任广西巡抚张鸣歧说什么也不同意蔡锷辞职。为了表示对蔡锷的信任，他又委派蔡锷任广西陆军小学堂总办。蔡锷凭着自己的责任感和事业心，仍然兢兢业业地投身于广西的军政事业。
蔡锷在广西悉心考察和研究边境防务，提出了许多积极的建议。在此期间，他写出了两部军事著作《越南重塞图说》和《桂边要塞图说》。1907年春，他陪同张鸣歧视察边防各地，巡行约4000余里，逐一记下了边关地区的山势和风土，并亲手草绘略图，还提出修建沿边炮台、整顿边防军备等建议，最后酝酿出关于加强广西防务的完整计划。除此之外，蔡锷在广西的重要活动是为当地培养军事人才。他在广西的主要职责就是训练新军。在担任广西陆军小学总办时，更是对学生进行严格训练和严格要求。广西陆军小学共办了四期，先后毕业的学生有数百人，李宗仁、白崇禧等后来名噪一时的人物，就是这个学校的毕业生。
创办陆军小学，是蔡锷回国初期所从事的军事活动中耗费精力最大的一项事业。陆军小学是培养陆军军官的预备学校，他认为陆军小学的学生都是有为的青年，是将来编练新军的骨干，决心尽全部心血将它办好，为军事救国培养人才。开办陆军小学时他只有26岁，但立志坚决，办事认真。他聘请的教员，大多是日本士官学校的毕业生，具有进步思想，德才兼优。陆军小学是当时的一流学堂，生活待遇优厚，投考陆军小学的条件十分严格。蔡锷不循私情，严格把关。据说李宗仁考上了第二期陆小，仅因为入学报到时迟了10分钟，即被取消了资格，延至第二年，考取了第三期，才得以入学。一位姓唐的学员由湖南来投靠第一期陆小，途中耽搁了十几天，误了考期。其父与蔡锷的父亲是世交，请求通融入学，但蔡锷坚持按规章制度办事，拒绝通融。由于蔡锷严格办学，注重实际，不尚空谈，使广西陆军小学成绩斐然，名声大振。学生毕业后，多考入各地的陆军中学。
关于蔡锷在广西陆军小学任总办的情况，李宗仁回忆说：我们的总办蔡锷将军有时来校视察，我们对他敬若神明。蔡将军文武双全，仪表堂堂。他骑马时，不一定自马身的侧面攀鞍而上，他喜欢用皮鞭向马身一扬，当马跑出十几步时，从马后飞步追上，两脚在地上一蹬，两手向前按住马臀，一纵而上。这匹昂首大马，看起来已够威风，而蔡将军纵身而上的轻松矫捷，更是惊人。我们当时仰看马上的蔡将军，真有“人中吕布，马中赤兔”之感。
蔡锷为人处事一向比较沉着冷静，对重大问题，不轻易表态，也不任意行动，但广西政界军界的复杂情况，使蔡锷的工作进行颇为不易，也曾遭受挫折。1911年春，蔡锷受已调至云贵任总督的李经羲的聘请，启程赴滇，继续激流勇进，揭开了自己戎马生涯的新篇章。