Provinsi Tsushima (対馬国code: ja is deprecated , tsushima no kuni) atau dikenal sebagai Taishū (対州code: ja is deprecated ) adalah provinsi lama Jepang yang menempati seluruh pulau Tsushima di Laut Jepang dan sekarang merupakan bagian dari prefektur Nagasaki.
Provinsi Tsushima terdiri dari 2 distrik: Kamiagata (上県) dan Shimoagata (下県). Ibu kota provinsi berada di Izuhara.
Provinsi Tsushima merupakan pulau strategis sebagai pusat kekuatan militer untuk menangkal invasi dari daratan Asia dan sebagai pusat perdagangan dengan semenanjung Korea. Tsushima kemungkinan besar sudah dijadikan provinsi kekaisaran Yamato sejak abad ke-5. Istana Kaneda dibangun di pulau Tsushima setelah Jepang mengalami kekalahan melawan Dinasti Tang dalam Pertempuran Hakusukinoe tahun 663.
Penguasa provinsi Tsushima adalah klan bergelar Tsushima no Kuni no miyatsuko yang memegang kekuasaan sampai di zaman Heian. Penguasaan Tsushima kemudian digantikan klan Ahiru hingga kekuasaan diambil alih klan So di akhir abad ke-15.
Di zaman Edo, Tsushima merupakan bagian dari wilayah han Tsushima Fuchu milik klan So yang memegang monopoli perdagangan dan diplomasi dengan dinasti Joseon.
Setelah penghapusan sistem wilayah han pada tahun 1871, Tsushima Fuchu berganti nama menjadi prefektur Izuhara untuk kemudian bergabung dengan prefektur Imari pada tahun yang sama. Pada tahun berikutnya (1872). prefektur Imari berganti nama menjadi prefektur Saga dan pulau Tsushima diserahkan kepada prefektur Nagasaki.
