Переговоры шли долго и мучительно. Обещание передать Хабомаи и Шикотан было минимальным условием, при котором в Токио соглашались подписать декларацию о восстановлении отношений. Если бы Москва на это не пошла, переговоры бы прервались. Передачи островов требовали и японские коммунисты – даже в те времена, когда КПСС являлась для них старшим братом.
С руководством компартии Японии встретился секретарь ЦК КПСС Суслов, ведавший отношениями с братскими партиями. Генеральный секретарь ЦК японской компартии Сандзо Носака втолковывал Суслову, что острова, конечно же, принадлежат Японии. Суслов отшутился по-партийному: когда Япония тоже станет социалистической, вопрос об островах отпадет сам собой…
19 октября 1956 года в Москве подписали совместную декларацию. Она прекращала состояние войны между двумя странами и восстанавливала дипломатические отношения. В декларации говорилось: «Союз Советских Социалистических Республик, идя навстречу пожеланиям Японии и учитывая интересы японского государства, соглашается на передачу Японии острова Хабомаи и острова Шикотан с тем, однако, что фактическая передача этих островов Японии будет произведена после заключения Мирного договора между СССР и Японией».
Подписание декларации в октябре 1956 года стало значительным событием прежде всего для Японии. Без согласия Советского Союза Япония не могла вступить в Организацию Объединенных Наций. Такое согласие Москва дала только после подписания декларации.
Декларация 1956 года считалась документом временным – до подписания полноценного договора. Но решить территориальную проблему не удалось. 27 января 1960 года Громыко вызвал к себе японского посла и вручил ему памятную записку, в которой было сказано: поскольку Япония подписала военный договор с США и лишилась самостоятельности, то передача ей островов Хабомаи и Шикотан стала невозможной.
В Японии кампания за возвращение северных территорий приобрела характер общенационального дела. Громыко твердо говорил, что территориального вопроса просто не существует.
В январе 1957 года Шепилов и Громыко получили послание главного редактора «Правды» Павла Алексеевича Сатюкова и его заместителя по международному разделу Георгия Александровича Жукова: