Sebelum berdirinya Polda Kep. Bangka Belitung, wilayah Bangka dan Belitung merupakan bagian dari Polda Sumatera Selatan yang terdiri dari 2 (dua) Polres yaitu Polres Bangka dan Polres Belitung. Selanjutnya seiring dengan pemekaran wilayah Propinsi Sumatera Selatan bahwa Kepulauan Bangka Belitung yang pada mulanya kabupaten berubah menjadi Propinsi berdasarkan Undang-Undang RI Nomor : 27 tahun 2000 menyatakan bahwa Kepulauan Bangka Belitung resmi menjadi Daerah Propinsi RI yang ke – 31 dan selanjutnya pada tanggal 9 Pebruari 2001, Menteri Dalam Negeri dan Otonomi Daerah Republik Indonesia melantik Bapak Amur Muchasim, Msi sebagai Pejabat Gubernur Kepulauan Bangka Belitung.
Dengan terbentuknya Propinsi Kepulauan Bangka Belitung maka sesuai dengan Surat Keputusan Kapolri No. Pol : Skep/07/XII/2000 tanggal 29 Desember 2000 tentang Pembentukan Polwil Kepulauan Bangka Belitung dan selanjutnya pada tanggal 11 Mei 2001 Kapolda Sumatera Selatan Mayjen Polisi Drs. Togar M. Sianipar, Msi, atas nama Kapolri meresmikan berdirinya Polwil Kepulauan Bangka Belitung yang berkedudukan di Polsek Sungailiat Kabupaten Bangka dan Melantik Kapolwil Kepulauan Bangka Belitung Kombes Pol. Drs Erwin TPL Tobing. Selanjutnya pada tanggal 27 Agustus 2001 Kantor sementara Polwil Kepulauan Bangka Belitung pindah dari Polsek Sungailiat ke jalan Bukit Intan No. 1 Pangkalpinang (gedung Milik Pemda Propinsi Kep. Babel) yang belum dilengkapi dengan sarana dan prasarana pendukung. Polwil Kep.Bangka Belitung membawahi 2 (dua) Polres yaitu Polres Bangka dengan Kapolres AKBP. Drs. Bachtiar H. Tambunan dan Polres Belitung dengan Kapolres AKBP. Drs. Iwan Hari Sugiarto. Selanjutnya berdasarkan Keputusan Kapolri No. Pol : Kep/39/IX/2002 tanggal 23 September 2002 Polres Bangka dipecah menjadi Polresta Pangkalpinang dan Polres Bangka dengan Kapolres AKBP. Drs. Lilik Purwanto
Setelah Polwil Kep. Bangka Belitung berdiri selama lebih kurang 2 tahun, maka berdasarkan Keputusan Kapolri No. Pol. : Kep/11/III/2003 tanggal 13 Maret 2003 status Polwil Kepulauan Bangka Belitung ditingkatkan menjadi Polda Kepulauan Bangka Belitung
