Dengan terjadinya pemekaran Pemekaran Provinsi Kepulauan Riau dari sebelumnya tergabung ke dalam wilayah Provinsi Riau, maka perlu dirasa untuk membentuk Kepolisian Daerah baru yang menaungi wilayah Kepulauan Riau. Sesuai dengan surat keputusan Kapolri dengan nomor: SKEP/09/III/2005, per tanggal 3 Maret 2005 dibentuklah Polda Kepri dengan status persiapan, yang sebelumnya tergabung kedalam Polda Riau. Pada awal terbentuk, terdapat 6 satker kewilayahan, yakni[1]:

  • Poltabes Barelang
  • Polresta Tanjungpinang
  • Polersta Tanjung Balai Karimun
  • Polres Natuna
  • Polres Lingga
  • Polres Bintan

Pada tanggal 21 Desember 2005, sesuai surat telegram Kapolri nomor ST/1078/XII/204, Kombes Pol Drs. Anton Bachrul Alam ditunjuk sebagai Kapolda Kepri[2]. Pada tanggal 20 Juli 2006, status Polda Kepri ditingkatkan dari persiapan menjadi tipe B2[3]. Selanjutnya di tahun 2007 dikeluarkan surat keputusan Kapolri tentang penetapan tipe Ditpolair menjadi tipe B. Di awal berdirinya, Polda Kepri berkedudukan di kantor Otorita Batam dengan status pinjam pakai[4]. Baru di tanggal 22 Agustus 2008, secara resmi berdiri Mapolda Kepri yang diresmikan pengunaanya oleh Kapolda Kepri saat itu Brigjen Pol Drs. Sutarman[5][6]. Mapolda Kepri beralamat di Jl. Hang Jebat Batu Besar Nongsa Batam.