Палац бойових мистецтв Японії був заснований 1964 року, у зв'язку із Токійськими олімпійськими іграми. Передумовою заснування стало включення дзюдо до програми ігор на 58-й сессії Міжнародного олімпійського комітету в червні 1961 року. За ініціативи Сьорікі Мацутаро та Кімури Токутаро, в Парламенті Японії була створена Парламентська асоціація за створення Палацу бойових мистецтв. До асоціації приєдналися 525 депутатів різних політичних партій. В січні 1962 року, за дозволу японської влади, була створена громадська організація «Палац бойових мистецтв Японії», що ставила на меті спорудження належної спеціальної зали для проведення змагань з японських традиційних бойових мистецтв. В серпні того ж року, в Палаті Представників, за ініціативи ліберал-демократів, демократів та соціалістів, було прийнято закон «Про Зал для японських традиційних видів спорту». За законом на будівництво Палацу було відведено ділянку в Північному дворі Едоського замку, неподалік від Імператорського палацу. Витрати на будівництво становили 2,2 мільярди єн.
Палац бойових мистецтв Японії було споруджено за зразком Палацу Снів в буддистському монастирі Хорюдзі. Будівля мала висоту 42 м і була увінчана великим 8-кутним дахом. Палац міг приймати до 15 тисяч глядачів і проводити змагання цілодобово. Офіційна церемонія відкриття відбулася 3 жовтня1964 року. Після відкриття Палац використовування не лише для спортивних змагань, а також для проведення різних громадських заходів і концертів.