Sejarah Kabupaten Natuna tidak dapat dipisahkan dari sejarah Kabupaten Kepulauan Riau, karena sebelum berdiri sendiri sebagai daerah otonomi, Kabupaten Natuna merupakan bahagian dan Wilayah Kepualauan Riau.

Berdasarkan Surat Keputusan Delegasi Republik Indonesia, Propinsi Sumatera Tengah tanggal 18 Mei 1956 menggabungkan diri ke dalam Wilayah Republik Indonesia, dan Kepulauan Riau diberi status Daerah Otonomi Tingkat II yang dikepalai Bupati sebagai kepala daerah yang membawahi 4 kewedanaan sebagai berikut:

• Kewedanaan Tanjungpinang, meliputi Kec. Bintan Selatan (termasuk Bintan Timur, Galang, Tanjungpinang Barat dan Tanjungpinang Timur).
• Kewedanaan Karimun, meliputi wilayah Kecamatan Karimun, Kundur dan Moro.
• Kewedanaan Lingga, meliputi wilayah Kecamatan Lingga, Singkep dan Senayang.
• Kewedanaan Pulau Tujuh, meliputi wilayah Kecamatan Jemaja, Siantan, Midai, Serasan, Tembelan, Bunguran Barat dan Bunguran Timur.

Kewedanaan Pulau Tujuh yang membawahi Kecamatan Jemaja, Siantan, Midai, Serasan, Tambelan, Bunguran Barat dan Bunguran Timur beserta kewedanaan laiannya dihapus berdasarkan Surat Keputusan Gubernur Kepala Daerah Tingkat I Riau tanggal 9 Agustus 1964 No. UP/247/5/1965. Berdasarkan ketetapan tersebut, terhitung 1 Januari 1966 semua daerah administrative kewedanaan dalam Kabupaten Kepulauan Riau dihapus.

Kabupaten Natuna dibentuk berdasarkan Undang-Undang No. 53 Tahun 1999 dari hasil pemekaran Kabupaten Kepulauan Riau, yang terdiri dari 6 Kecamatan yaitu Kecamatan Bunguran Timur, Bunguran Barat, Jemaja, Siantan, Midai, dan Serasan dan satu Kecamatan Pembantu Tebang Ladan.

Seiring dengan kewenangan otonomi daerah, Kabupaten Natuna kemudian melakukan pemekaran daerah kecamatan, yang hingga tahun 2004 menjadi 10 kecamatan dengan penambahan, Kecamatan Palmatak, Subi, Bunguran Utara, dan Pulau Laut dengan jumlah kelurahan/desa sebanyak 53.

Hingga tahun 2007 ini Kabupaten Natuna telah memiliki 16 Kecamatan. 6 Kecamatan pemekaran baru itu diantaranya adalah Kecamatan Pulau Tiga, Bunguran Timur Laut, Bunguran Tengah, Siantan Selatan, Siantan Timur dan Jemaja Timur dengan total jumlah kelurahan/desa sebanyak 75.