光緒二十三年（1897年）正月初四為張蔭桓生日，黃遵憲作《樵丈尚書六十有一賦詩敬祝》，詩雲：“入丁出丙壽星祥，四國傳誇天上張。冠冕南州想風度，樞機北鬥在文昌。金城引馬迎朝爽，銀漢歸槎照夜光。揮塵雄譚磨劍氣，獨因憂國鬢蒼蒼。”[22]三月，張蔭桓奉命赴英參加維多利亞女王登基60周年慶典活動。臨行前黃遵憲又賦詩《題樵野丈運甓齋話別圖》，回顧了兩人20多年來的交往，詩中表達了對張蔭桓的欽佩與感激之情，[23]可視為黃、張關係的真實寫照。
次年五月，在京閑居九個月之後的黃遵憲終被授以湖南長寶鹽法道。此次放缺與軍機大臣翁同龢的努力有關。翁氏日記光緒二十二年九月二十六日（1896年11月1日）記：“黃公度（遵憲）來，以所撰《日本國誌》見贈。”[24]光緒二十三年五月三十日（1897年6月29日）記：“黃公度遵憲，新授湖南鹽道，來長談，重在延德人、練德法。”[25]同年六月十五日（7月14日）又記：“晚黃公度來辭行，明日起身矣，長談：第一事，開學堂；二事緩海軍，急陸軍，十五萬人已足；三事海軍用守不用戰。合船無用，郎哩亦無用。三大可慮：一教案，一流寇，一歐洲戰事，有一於此，中國必有瓜分之勢。”[26]從這些記載看，翁對黃的才具和見識也是較為欣賞的。他對黃遵憲遭德方拒絕一事也曾設法補救。不過，翁對黃的賞識很難說與張蔭桓毫無關係。甲午至戊戌間翁、張二人關係密切，翁“倚之如左右手，凡事必谘而後行”。[27]張被稱為“甲午至戊戌間幕後大人物”，即與受到翁的信任有直接關係。光緒帝既已對黃遵憲深簡在心，翁氏位居樞垣，從張之議一力保舉亦在情理之中。
黃遵憲抵達湖南後，巡撫陳寶箴“讚變法，公度乃以其平日之學發紓之”，“凡湖南一切新政，皆賴其力”。[28]開時務學堂，特聘梁啟超為總教習，設立保衛局等新政措施均有黃氏的參與，在陳、黃、梁、譚（嗣同）等人的倡導和主持下，湖南成為當時最有生氣的省份。是年底，德國侵占膠州灣事件發生後，以挽救民族危亡為主題的變法圖強運動在北京迅速興起，與湖南新政成相輔之勢。黃遵憲與張蔭桓的政治合作關係也進入了最重要的時期。