Dalam situasi politik yang tidak stabil pada tahun 1950-an, berpengaruh besar terhadap organisasi militer yang kemudian melahirkan kekacauan kekacuan nasional. Beberapa kelompok separatis bersenjata muncul di mana-mana. Saat itulah satuan-satuan Mobrig yang setia kepada Republik ini secara aktif turut melakukan penumpasan dan pengamanan diberbagai daerah di tanah air. Dari rangkaian sejarah ini, terbentuk Kepolisian Daerah Kalimantan Selatan.
Pengabdian Mobrig dalam melaksanakan tugas Negara tidak pernah surut. Sekitar tahun 1953, di Kalimantan Selatan, satuan Mobrig yang berasal kesatuan Surabaya dikerahkan untuk memadamkan pemberontakan rakyat pimpinan Letnan Dua Ibnu Hajar, Komandan Pasukan Pengempur Divisi IV ALRI di Kalimantan Selatan. Satuan Mobrig yang berasal dari kesatuan Surabaya itulah yang menjadi cikal bakal berdirinya Polda Kalimantan Selatan
Kekecewaan yang berulang-ulang telah membuat Ibnu Hajar pada bulan Oktober 1950 di Kalimantan Selatan membentuk Kesatuan Rakyat yang Tertindas (KRyT) dan menyatakan gerakannya sebagai bagian dari Negara Islam Indonesia (NII) dengan wilayah pergerakannya di daerah Hulu Sungai sepanjang kawasan pegungungan Maratus pada wilayah Kalimantan Selatan. Selain kelompok Ibnu Hajar, ada juga kelompok yang dikenal dengan nama Gerakan Mandau Talawang Panca Sila (GMTPS), pimpinan Christian Simbar di daerah sepanjang perairan Sungai Barito di wilayah Kalimantan Tengah. Gerakan Ibnu Hajar dengan KRyTnya dalam aksinya menggunakan taktik perang gerilya. Aktivitas aksinya semakin meluas ke wilayah-wilayah Barabai, Birayang, Batumandi, Paringin, Kelua dan Kandangan.
Selain melalui kekuatan bersenjata dalam menghadapi pemberontakan Ibnu Hajar, pemerintah pusat juga menggunakan pendekatan melalui tokoh-tokoh kharismatik lokal seperti Hasan Basery (mantan komandannyaIbnu Hajar) dan Idham Khalid seorang politikus dari Nahdiatul Ulama (NU) untuk membujuk Ibnu Hajar dan KRyTnya agar meletakan senjata dan kembali ke pangkuan Ibu Pertiwi. Awalnya Ibnu Hajar bersedia untuk menyerahkan diri namun setelah menyerahkan diri, Ibnu Hajar akhirnya melarikan diri dan melakukan pemberontakan kembal. Selanjutnya pemerintah melakukan tindakan yang tegas sehingga pada akhir tahun 1959 Ibnu Hajar beserta seluruh anggota gerombolannya tertangkap. Ibnu Hajar sendiri akhirnya dihukum mati pada juii tahun 1963.
Selama mengatasi pemberontakan Ibnu Hajar dan Simbar, berbagai peristiwa heroik terjadi. Salah satunya adalah peristiwa tragis dan mengharukan bagi Bhanyangkari Polda Kalsel. Pada tanggal 28 September 1953 Mathilda Batlayeri, seorang Bhayangkari gugur bersama-sama ketiga anak dan janin dalam kandungannya pada saat membantu mempertahankan Pos/Asrama Polisi yang diserang oleh gerombolan KRyT.
Secara formal, bersamaan datangnya pasukan Mobrig, Kepolisian Kalimantan pada 1953 terbentuk dan berkedudukan pertama di Banjarmasi. Pada awalnya Polda Kalsel dikenal dengan sebutan Kepolisian Keresidenan Kalimantan, dimana pada saat itu Keresidenan Kalimantan Selatan dan Kalimantan Tengah menjadi satu berkedudukan di Banjarmasin. Baru pada 23 Mei 1957, Keresidenan Kalimantan Tengah resmi berdiri sendiri menjadi Provinsi dengan Ibukota Palangkaraya. Namun Kepolisian Kalimantan masih mencakup Kalimantan Selatan dan Kalimantan Tengah.
Berdasarkan SK Perdana Menteri RI, tanggal 12 Januari 1959, sebutan untuk Kepolisian di Kalimantan yang semula Kepolisian Provinsi (KPPPROP) Kalimantan, berubah menjadi Kepolisian Komisariat (KPKOM). Sementara itu sebutan untuk Kepolisian Resort disingkat KPPRES, dimana pada waktu itu KPKOM Kalsel membawahi 7 KPPRES. Dan berdasarkan Keputusan Presiden RI tertanggal 12 April 1962, nama Kepolisian Negara kembali berubah menjadi Angkatan Kepolisian Republik Indonesia. Menyusul perubahan tersebut, maka sebutan Kepala Kepolisian Negara (yang sekarang disebut Kapolri) berubah menjadi Menteri Panglima Angkatan Kepolisian Republik Indonesia disingkat Menpangak.
Maka sejak itu juga sebutan Markas Besar AKRI disingkat MARAK. Sebutan untuk Kepolidian di tingkat Provinsi menjadi Komando Daerah Angkatan Kepolisian disingkat KOMDAK. Di tingkat Kabupaten di sebut Komando Resort Kepolisian disingkat KOMRES, ditingkat Kecamatan disebut Komando Dsitrik atau KOMDIS. Sedangkan untuk pimpinan Kepolisian di tingkat KOMDAK adalah Panglima Komando Daerah Angkatan Kepolisian disingkat Pangdak, di tingkat KOMRES adalah Komandan Resort (Danres) dan di tingkat KOMSEK yaitu Dansek atau Dandis. Sejak itulah Komdak XIII/Kalsel terbentuk.
Pada tahun 1962 terjadi musibah kebaaran yang menimpa Markas Komdak XIII/Kalsel dan menghanguskan seluruh bangunan beserta isinya. Pada bulan Juli 1963, Ibnu Khajar dan pengikutnya meyerahkan diri di Desa Ambulun Hulu Sungai Selatan. Pada tahun yang sama juga, berdirilah lembaga pendidikan di Banjarbaru yang waktu itu bernama Sekolah Angkatan Kepolisian disingkat SAK (sekarang SPN). berdasarkan Surat Keputusan Mehankam/Pangab, pada tahun 1974 dilakukan likuidasi antara Komdak XIII/Kalsel dengan Komdak XII/Kaltengmenjadi satu komando dengan sebutan KOMDAK XIII/KALRA (Kalimantan Tenggara) dengan Brigjen Pol. Drs. R. Hardono sebagai Kadapol XIII/Kalra yang pertama. Komdak XIII/Kalrayang berstatus tipe B itu membawahi 16 Komres dan 129 Komsek
Sebutan Polda Kalselteng dimulai sejak reorganisasi Polri di tahun 1984. Keudian berdasarkan Surat Keputusan Pangab nomor : Kep/11/X/1992 tanggal 5 Otober 1992, terjadi likuidasi Polda Kaselteng menjadi Polda Kalsel dan Polda Kalteng yang realisasinya dilaksanakan pada penghujung tahun anggaran 1994/1995. Pemisahan ini ditandai dengan penyerahan Pataka “TUNGGAL DHARMA VISUDA” untuk Polda Kalsel dan Pataka “MANUNGGAL DHARMA CARYA JAYA” untuk Polda Kalteng. Namun dampaknya adalah status Polda Kalsel yang sebelumnya type “B” dipimpin oleh seorang Brigjen, sejak likuidasi tersebut turun menjadi type “C” dan dipimpin oleh seorang Kolonel.
Pada perkembangan berikutnya, berdasarkan keputusan Menhankam pada bulan Oktober 1999, dikukuhkan pada tanggal 19 Oktober 1999 status Polda Kalsel ditingkatkan kembali menjadi type “B” bersama-sama dengan Polda Kalbar, DIY, Sulut, Bali, Aceh, Riau, Jambi, NTT dan Maluku. Seiring naiknya status maka dengan sendirinya Polda Kalsel kembali dipimpin oleh seorang polisi berpangat Brigjen Pol hingga sekarang.
Perubahan status Polda Kalsel dan Polda-Polda lainnya sangat berkaitan dengan tuntutan reformasi di dalam tubuh Polri berkenaan dengan pemisahan Polri dari ABRI pada tanggal 1 April 1999 yang menginginkan kinerja Polri khususnya Polda Kalsel menjadi lebih mandiri dan proaktif.