Ельцин посетил Японию лишь в октябре 1993 года, после того как она – уступив давлению США и членов Большой семерки – пообещала предоставить экономическую помощь России в размере 1,8 млрд долларов как часть пакета Большой семерки и выразила готовность занять более гибкую позицию по вопросу о спорных территориях (Meyer 1993: 965). На саммите с участием премьер-министра Японии Хосокавы Ельцин подчеркнул желание России развивать отношения с Японией на основе «законности и справедливости». Эти два понятия вошли в японский политический дискурс и стали ключевыми понятиями в дискуссии о двусторонних отношениях, особенно в вопросе о спорных территориях. В двусторонней Токийской декларации Ельцин обязался разрешить территориальный спор и пообещал исполнять соглашения, подписанные Советским Союзом. Однако он отказался отдельно упомянуть Совместную декларацию 1956 года, в которой СССР обещал передать Японии два острова после заключения постоянного мирного договора. Впрочем, важно отметить, что во время своего визита Ельцин публично извинился за советское интернирование японских военнопленных после Второй мировой войны. Японский истеблишмент приветствовал этот жест как знак значительных изменений в русско-японских отношениях (Hasegawa 2000a: 184–186).
Примерно в это время общий дискурс о России стал избавляться от прежней социокультурной конструкции. С этой поры социокультурная конструкция использовалась главным образом в территориальном споре. В то же время в большинстве дебатов стала набирать силу концепция России как новой страны. Постепенно Россию стали называть «переродившейся Россией» (shinsei roshia), чтобы подчеркнуть ее непричастность как к СССР, так и к «исторической» России (см., например, речь министра иностранных дел Хаты Цутому в палате представителей 14 октября 1993 года; NDL).
Вследствие политической нестабильности в обеих странах в промежутке между визитом Ельцина и 1996 годом никаких особых подвижек в двусторонних отношениях не произошло. В России наблюдался подъем националистических настроений, популярность и политическая мощь Ельцина значительно ослабли, и большинство мест в парламенте после выборов 1995 года принадлежали оппозиции, состоявшей из коммунистов и националистов. В Японии в 1994 году к власти пришло коалиционное правительство, составленное из представителей двух конкурирующих партий – Социалистической и Либерально-демократической; его возглавил социалист Мураяма Томи’ити. Это правительство оставалось у власти в течение двух лет, однако отсутствие полного единства не позволило кабинету Муруямы добиться какого-либо прогресса в области внешней политики.