Cho đến năm 1990, ông vẫn thường xuyên tiếp xúc với một nhà ngoại giao Liên Xô. Anh ta đã kết thúc mối quan hệ này sau khi được Cơ quan An ninh Cảnh sát Na Uy thông báo rằng người liên hệ của anh ta là một đặc vụ KGB, cảnh báo anh ta không được tiếp tục liên lạc. Mật danh mà KGB đặt cho Stoltenberg là "Steklov".