1895 年，萨哈林岛（库页岛）山谷（插画作品）

1859年7月下旬，穆拉维约夫在先送美国公使、再送属下小布进京后，驶离渤海湾。根据来时与日方的约定，穆督先至北海道南端的函馆，带上领事加什凯维奇赴江户谈判。所谓黑龙江舰队的9艘舰只跟随前往，由于他乘坐的“亚美利加号”航速较快，4艘轻型巡航舰和其他补给舰跟不上，只好走走停停，惹得老穆一路没少发火。这次俄日两国的议题是中国库页岛的归属。由于清廷的长期漠视、吉林将军衙门的毫无作为，岛上各族同胞基本是一种自生自灭的状态，该岛遂成为两个邻国争夺的一块肥肉。

两个邻国都惦记着这个北方大岛，当时的想法则略有不同：日本人希望得到库页岛的南部，而俄国人则要拥有全岛。这项谈判本不是穆拉维约夫的职责，但他主动请缨，意欲再搞一次“炮舰外交”，以为日本官员与清朝大员一样，以武力恐吓即会屈服。而因他去年在瑷珲的逼签成功，沙皇颇有几分信任，沙俄外交部不便阻拦，很快寄来了全权证书，于是这位总督大人摇身一变，成了领衔赴日谈判的特使。

大约在当年的8月中旬，老穆带着他的舰队抵达日本首都江户。这里用“大约”，乃因《穆拉维约夫－阿穆尔斯基伯爵》中没有这次谈判的准确时间，且不要说会谈细节，就连大概的过程也没有，与对瑷珲签约的记述之详形成鲜明对比。幸而在该书附录中，能看到穆督的几封相关信件，也附有他与日本全权代表第一次会晤时的发言，通过这些能了解到一些情况。在江户的谈判桌上，穆拉维约夫仍是一副蛮横口气，甚至比对待奕山更过分。他显然提前做过一些功课，预料到日方必以在南库页的实际存在为词，一上来就直接否定，说：

日本渔民长期以来在萨哈林岛，亦即桦太岛南端的阿尼瓦湾捕鱼。这两个古老的名称表明，这个岛同萨哈连乌拉（我们称之为阿穆尔）同出一源，萨哈林岛近170年来，即早在日本渔民开始在那里捕鱼之前，曾归中国所有。但在更早以前，萨哈连乌拉是属于俄国的，因而萨哈林岛当然也属于俄国。俄中两国为保持友好关系，秉公而断，双方共同议定，萨哈连乌拉（阿穆尔）仍然划归俄国所有。