The bilateral ties between the two countries has it origins back to 1920, when Japan assumed control over Germany Empire's island colonies in the Pacific which included present-day Micronesia, the Marshall Islands, the Northern Marianas and Palau. The islands became part of the South Pacific Mandate under the League of Nations and Koror was designated as the administrative center of the mandate. Under Japanese rule, Palau experience significant development of its fishing, agriculture and mining industry. Palau achieved self-sufficiency of some degree during the period. Palau also served as a Japanese military base during the World War II. Japanese administration over the islands ended following the defeat of Japan in the World War II. The South Pacific Mandate became the Trust Territory of the Pacific Islands and it was administrated by the United States.
Japan recognized the independence of Palau from the United States on October 1, 1994 and established formal relations with Palau on the same year on November 2. The Japanese embassy in Koror opened in 1999.
As a former Japanese colony, Palau was influenced by Japanese culture. Contemporary Palauan has many words derived from Japanese such as "daijobu", "okyaku", "denki" and "senkyo". Local cuisine has also been influenced by the Japanese.
Palau-based tuna shipping companies mainly export sashimi grade tuna to Japan. Licensing of fishing vessels from Japan remains a source of foreign exchange between Palau and Japan.
Palau has supported Japan's whaling rights in the past but has since abandon its support in June 2010 in favor of catch quota proposal being considered by the International Whaling Commission. Johnson Toribiong asserted that his country's policy change won't affect Japan-Palau relations and claimed that Japan is "mature enough" to accept Palau's stand on whaling. 
Japan has sent the Japan Mine Action Service to Palau to clear World War II bombs sitting dormant in Palau's seabed. The clearing operations started in May 2013 and will take about a year and half.
- "Embassy of Japan in the Republic of Palau". Palau.emb-japan.go.jp. 2006-03-23. Retrieved 2013-09-02.
- "Countries - Pacific - Republic of Palau - Information Paper - NZ Ministry of Foreign Affairs and Trade". Mfat.govt.nz. Retrieved 2013-09-02.