Tsushima Province (対馬国 Tsushima-no kuni?) was an old province of Japan on Tsushima Island which occupied the area corresponding to modern-day Tsushima, Nagasaki. It was sometimes called Taishū (対州?) .
The origin of Tsushima Province is unclear. It is possible that Tsushima was recognized as a province of the Yamato Court in the 5th century. Under the Ritsuryō system, Tsushima formally became a province.
Tsushima Province has been a strategic area that took a major role in the national defense against possible invasions from the continent and in trade with Korea. After Japan was defeated by Tang dynasty at the Battle of Baekgang in 663, Kaneda Castle was constructed on this island.
Tsushima Province had been controlled by the Tsushima no Kuni no miyatsuko until the Heian Period. This clan was later replaced by the Ahiru clan. The Sō clan rose to power around the middle 13th century and seized control of the entire island in the late 15th century. During the Edo Period, Tsushima Province was dominated by the Tsushima Fuchu domain (Izuhara domain) of the So clan. It was put in charge of diplomacy and monopolized trade with the Joseon Dynasty of Korea.