『해동제국기』는 1471년(성종 2) 신숙주(申叔舟)가 통신사행의 서장관(書狀官)으로 직접 일본에 다녀온 경험과 오랜 기간 예조판서로서 쌓은 외교 경험을 바탕으로 조선과 일본의 서적을 참고하여 완성한 책이다. ‘해동제국’은 일본 본국·구주(九州) 및 대마도·일기도(壹岐島)와 유구국(琉球國)을 총칭하는 말이다. 『해동제국기』에는 일본, 대마도, 일기도, 유구의 역사, 지리, 정치, 문화, 풍속, 사신 왕래의 연혁과 조선의 사신 접대 규정이 정리되어 있으며, 각 지역의 상세 지도가 수록되어 있다. 『해동제국기』는 조선시대 통신사행의 지침서이자 대일 외교의 준거가 되었다. 그러나 임진왜란이 끝나가고 명·일간에 정전 협상이 시작되던 1598년(선조 31) 9월, 명의 찬획주사(贊晝主事) 정응태(丁應泰)가 『해동제국기』를 근거로 명 황제에게 조선이 일본과의 관계를 은폐하고 천조(天朝)를 우롱했다고 참소(讒訴) 했고, 무고 사건으로 종결될 때까지 조선은 어려움을 겪기도 했다.

신숙주의 본관은 고령(高靈)이며, 자는 범옹(泛翁), 호는 보한재(保閑齋)·희현당(希賢堂)이다. 1438년(세종 20) 진사시 초시와 복시에 모두 장원으로 급제했고, 이어서 생원시에도 합격했다. 1439년(세종 21)에는 문과에 급제하여 전농시(典農寺)의 종7품 직장(直長)이 되었고, 1441년(세종 23)에는 집현전의 부수찬이 되었다. 문장이 뛰어나고 외국어에도 능통했던 그는 약 40년 동안 세종, 문종, 단종, 세조, 예종, 성종 등 여섯 명의 국왕을 거치며 많은 업적을 남겼다.

1443년(세조 25)에는 통신사행의 서장관으로 일본에 다녀왔고, 귀국하는 길에 이예(李藝)와 함께 쓰시마(對馬島)에서 「계해약조(癸亥約條)」를 체결했다. 1452년(문종 2)에는 수양대군의 서장관으로 명에 가는 사은사(謝恩使)행에 동행했고, 1455년(세조 1)에는 세조의 왕위 찬탈을 도운 후 세조의 즉위 승인을 구하는 사자로 명에 파견되었다. 1460년(세조 6)에는 강원도 함길도의 도체찰사(都體察使)로서 북방의 여진족 토벌에 공을 세웠다.

한편, 신숙주는 집현전이 배출한 최정예 학자 관료로서 국가적으로 학문 활동과 편찬 사업이 활발했던 세종대부터 전적(典籍) 편찬에 주도적으로 참여했다. 『세조실록』, 『예종실록』 뿐만 아니라 조선의 역대 국왕들의 정치 활동 가운데서 모범이 되는 사실을 뽑아 적은 편년체 역사책인 『국조보감(國朝寶鑑)』을 편찬했다. 또한 다섯 가지 의례를 규정한 『국조오례의(國朝五禮儀)』를 교정·간행했고, 단군조선에서 고려 말까지의 역사를 편년체로 기록한 사서인 『동국통감(東國通鑑)』의 편찬을 총괄하고 수정에도 참여했다. 1461년(세조 7) 세조의 명으로 저술한 『북정록(北征錄)』에서는 동북 방면으로 자주 침입하는 여진족의 토벌책을 제시하기도 했다. 1471년(성종 2)에는 성종의 명으로 외교관으로서의 지식을 응축한 『해동제국기』를 편찬했다.

신숙주가 『해동제국기』를 편찬할 당시의 조일관계는 계해약조 체결 이후에도 계속된 사자 선박의 증가와 일본인 내항자(來降者)에 대한 접대와 지급되는 양식 등으로 인해 조선에 큰 경제적 부담이 되는 등 끊임없이 문제가 발생하고 있었다. 따라서 조선은 일본인에 대한 통제책을 보완하기 위해 사자 선박 수, 상경 인원수, 포구에 머무는 일수, 일본인에 대한 접대 규정을 정비할 필요가 있었다. 이에 성종은 신숙주에게 해동 여러 나라들과 사신이 왕래하던 옛 관례와 그들을 숙박시키는 일, 곡식을 지급하는 일, 예절에 맞게 접대하던 사례 등을 편찬하여 올리라고 명령했다.

“대체로 이웃 나라와 사귀어서 사신이 왕래하고, 풍속이 다른 나라 사람을 편안하게 접대하기 위해서는 반드시 그 실정을 알아야만 예절을 다할 수 있고, 예절을 다해야만 그 마음을 다했다고 할 수 있습니다. 이에 우리 주상 전하께서 신(臣) 숙주(叔舟)에게 명하여 해동 여러 나라들과 사신이 왕래하던 옛 관례와 그들을 숙박시키는 일, 곡식을 지급하는 일, 예절에 맞게 접대하던 사례 등을 편찬하여 올리라고 하셨습니다.(『海東諸國記』 序文)

신숙주의 졸기에는 “오랫동안 예조를 관장하여 사대교린(事大交隣)을 자신의 소임으로 삼아 사명(詞命)이 그의 손에서 많이 나왔다”라고 되어 있다. 이는 그가 오랜 기간 예조의 일을 관장하며 조선의 외교정책 입안자 및 책임자로서의 역할을 담당했음을 보여준다. 이 과정에서 그는 수많은 외교문서를 접하고, 외국 사신들을 접대하며 접촉했던 경험을 통해 외교적 지식을 축적했다. 이러한 이유로 신숙주는 해동 여러 나라의 왕래와 조선에서 이들을 대접했던 규례를 정리할 적임자였다.

국왕의 명에 따라 신숙주는 1471년 『해동제국기』를 편찬했다. 『해동제국기』 서문에 “대체로 이웃 나라와 사귀어서 사신이 왕래하고, 풍속이 다른 나라 사람을 편안하게 접대하기 위해서는 반드시 그 실정을 알아야만 예절을 다할 수 있고, 예절을 다해야만 그 마음을 다했다고 할 수 있습니다. 이에 우리 주상 전하께서 신(臣) 숙주(叔舟)에게 명하여 해동 여러 나라들과 사신이 왕래하던 옛 관례와 그들을 숙박시키는 일, 곡식을 지급하는 일, 예절에 맞게 접대하던 사례 등을 편찬하여 올리라고 하셨습니다. 신은 명을 받고 두려움을 이기지 못하여 삼가 옛 문헌을 상고하고 보고 들은 것을 참고하여 그 지세를 그리고, 대략 세계(世係)의 본말과 풍토의 숭상하는 바를 서술하고, 우리나라에서 응접하던 절차까지 덧붙여서 편집하여 책을 만들어 올립니다”라고 되어 있다.

이와 같이 신숙주는 1443년에 통신사의 서장관으로 직접 일본에 다녀온 경험과, 오랜 기간 동안 예조의 일을 관장하며 쌓은 많은 외교적 경험을 토대로 조선과 일본의 옛 문헌을 참고하여 일본의 역사, 지리, 풍속과 조선의 접대 규정 등을 내용으로 하는 『해동제국기』를 완성했다. 이후 『해동제국기』는 조선에서 일본의 지리, 환경, 일본인의 혈통을 파악하는 기본자료가 되었고, 통신사행의 지침서로서 이후 저술되는 통신사행록에도 많은 영향을 주었다. 또한 일본과 유구왕국 등 외국에 대한 접대 의례의 준거가 되었고, 북방 야인들에 관한 책자를 만드는 데에도 참고 자료로 이용되었다.

『해동제국기』는 첫 부분에 신숙주의 서문과 범례(凡例)가 있으며, 본문은 「해동제국총도(海東諸國總圖)」를 비롯한 7매의 지도와 「일본국기(日本國紀)」, 「유구국기(琉球國紀)」, 「조선응접기(朝聘應接紀)」 등 세 부분으로 구성되어 있다. 마지막 부분에 「부록(附錄)」이 실려 있다.

지도는 해동제국 전체를 그린 「해동제국총도」와 일본 본토 및 각 지역을 그린 「일본본국도(日本本國圖)」, 「서해도구주도(西海道九州圖)」, 「일기도도(壹岐島圖)」, 「대마도도(對馬島圖)」, 「유구국도(琉球國圖)」, 「조선삼포도(朝鮮三浦圖)」 등이 수록되어 있으며, 매우 세밀하고 정확하게 묘사되어 있다. 또한 조선의 웅천 제포지도(熊川薺浦之圖), 동래 부산포지도(東萊富山浦之圖), 울산 염포지도(蔚山鹽浦之圖)가 그려져 있고, 각 포구의 사정과 경성까지의 거리와 일정이 기록되어 있다.

「일본국기」는 천황대 서(天皇代 序), 국왕대 서(國王代 序), 국속(國俗), 도로리수(道路里數), 팔도육십육주(八道六十六州)/대마도·일기도(對馬島壹岐島 附)로 구성되어 있다. 내용은 일본 천황(天皇)과 쇼군(將軍)의 세계(世系), 풍속, 부산포에서 일본 주요 지역까지의 거리, 일본의 팔도 66주와 대마도·일기도 등의 연혁이 정리되어 있다. 특히 조선과 일본 66주와의 통교 사례 가운데 서해도 구주(西海道 九州)와 대마도에 대해 상세히 정리했고, 산양도(山陽道) 주방주(周防州) 대내전(大內殿, 오우치씨)에 대해서는 그들이 백제의 후예라는 점을 언급했다.

「유구국기」는 국왕대(國王代), 국도(國都), 국속(國俗), 도로리수(道路里數)로 구성되어 있다. 내용은 국왕의 세계, 수도, 풍속, 부산포에서 유구 주요 지역까지의 거리 등이 수록되어 있다. 특히 땅이 좁고 인구가 많기 때문에 남만(南蠻), 중국을 비롯하여 일본과 조선을 대상으로 해상무역이 발달했다는 것과 유황이 특산물이라는 점, 의복이 일본과 비슷하다는 점을 언급했다.

「조선응접기」는 조일 외교의 규정과 의례 등을 정리한 것이다. 일본에서 오는 사신의 선박 수와 인원, 일본 사신에 대한 영접과 환송, 서울까지 왕래하는 노정(路程), 삼포(三浦)와 서울에서 거행되는 각종 연회, 일본 사신에게 하사하는 물품, 선박 수리에 대한 물자 지급 및 항해 기간의 물자 지급, 조일 간에 체결한 각종 조약의 내용이 수록되어 있다.

현재 『해동제국기』는 금속활자본과 목활자본, 석판본 및 영인본이 전하고 있다. 또한 여러 종류의 필사본과 이 책을 합본하여 편집한 연활자본이 있다. 필사본은 한국에 6종, 일본에 약 20종의 필사본 이본이, 미국·프랑스·대만에도 필사본이 있다. 한국에 있는 6종의 필사본 가운데 국립중앙도서관본과 서울대학교본, 장서각본과 규장각본 등 4종은 일본인이 필사한 것이며, 육당문고의 2종은 한국인이 필사한 것이다. 또한 금속활자본이 현존하는데, 국내에서는 국사편찬위원회 소장본이 유일하며, 1926년 쓰시마 종가로부터 구입한 문서에 포함되어 있었다. 일본에는 도쿄대 사료편찬소의 구(舊) 요안인(養安院)장서본, 국립공문서관의 내각문고본(內閣文庫本), 난바 마쓰타로 본(南波松太郞本) 등 3종의 금속활자본이 있으며, 이 가운데 사료편찬소 소장본은 임진왜란 당시 일본으로 유출된 것으로 파악되고 있다.

1598년 9월 명의 찬획주사 정응태는 130년 전에 찬술된 『해동제국기』를 근거로 조선이 일본과의 관계를 은폐하고 천조를 우롱했다고 명 황제에게 참소했다. 이로 인해 조명관계에는 전례 없는 긴장 국면을 맞았다. 『해동제국기』의 존재가 드러난 것은 그동안 일본과의 통교 관계를 비밀에 부쳐온 조선에게 큰 문제였다. 일본과의 통교 사실이 알려지게 되면서, 조선과 일본의 왜란 공모에 대한 명의 의심을 증폭시키는 단서가 될 수 있었다. 명 황제에 대한 모반 혐의는 명과 조공 책봉 관계를 맺고 사대의 예로 명을 대우해 온 조선에게 국가의 존망을 걸어야 할 중대한 문제였다.

조선에서는 정응태의 참소에 대해 진주사를 파견하여 조선의 모반 혐의를 변론하고, 선조의 7일간 정무 중단이라는 과감한 대응을 통해 조선의 모반 혐의가 무고(誣告)임을 적극 주장했다. 결국 정응태의 참소는 무고로 결론 나면서 조선은 혐의를 벗었다. 이후 조선은 정응태가 『해동제국기』를 입수한 경위를 끝까지 추적하고, 관련자를 조사하여 처벌했다.