Национальный дискурс безопасности стал существенно меняться в 1996 году, когда произошел упомянутый выше Тайваньский кризис. Китайские испытания ракет над Тайваньским проливом и последовавшее развертывание там военно-морских сил США очевидно затмили роль России в программе безопасности Японии. В то же время в 1996-м и последующие годы происходило развитие японо-российских отношений в области безопасности. В частности, во время визита министра иностранных дел России Евгения Примакова в Токио в ноябре 1996 года было заявлено о сокращении российского военного присутствия на спорных островах; состоялся визит главы японского Агентства обороны Усуи Хидео (тогда этот пост был эквивалентен министру обороны) в Россию и ответный визит министра обороны России Игоря Родионова в Токио в следующем году. Во время этого визита Родионов заявил, что Россия не рассматривает Японию или японо-американский альянс как военную угрозу (Sarkisov 2000: 219–221). Этот диалог получил официальное развитие два года спустя во время визита главы агентства обороны Нороты Хосей в Москву в 1999 году и был подтвержден в Плане действий, подписанных Коидзуими и Путиным в 2003 году.
Важно отметить, что диалог по вопросам обороны вовсе не представлял собой исключительно риторическое упражнение: он реализовывался на различных уровнях деятельности военного истеблишмента. В 1996–1998 годах Россию дважды посещал глава Агентства обороны Японии и один раз глава ее штаба. В 1996 году пилотов японских Сил самообороны приглашали на учения в Россию, где они летали на самых современных реактивных истребителях, получив доступ к новейшим российским военным технологиям (Ferguson 2008: 86). Более того, в 1996 году корабли военного флота Японии участвовали в церемонии празднования 300-летия российского флота, а на следующий год в Японию приплыл российский эсминец. Военные флоты проводили совместные учения в 1998 и 1999 годах. Эти учения были глубоко символичными, поскольку впервые в своей истории японский флот проводил совместные учения не с США (Izuyama, Hyodo, Matsuura 2001: 17). Начиная с 1998 года эти совместные мероприятия стали регулярными. К ним относятся визиты главы Российского генштаба и командующего российским ВМФ и ответные визиты главы агентства обороны и председателя совета совместного штаба; дружеские визиты российских и японских военных судов; совместное участие в поисково-спасательных операциях и обмен оборонными исследованиями (NIDS 2000: 254–255). Военное сообщество Японии расценило эти события как позитивные шаги к нормализации двусторонних отношений (Ogawa et al. 1999: 30–35, а также речь главы Агентства обороны Кавары Цутому в палате представителей, Комитет национальной обороны, 12 апреля 2000 года, NDL). Более того, начиная с 2003 года визитами обмениваются и военные из сухопутных Сил самообороны Северного военного округа (который граничит с Россией и «традиционно» наиболее подозрительно относится к российским инициативам)