Baada ya Mapinduzi Matukufu ya 1964, ambayo yaliongozwa na Chama Cha Afro Shirazi Party (ASP) chini ya Jamadari wa Mapinduzi na Rais wa kwanza wa Zanzibar marehemu Mzee Abeid Aman Karume, Serikali ya Mapinduzi ya Zanzibar ilianzisha vyombo vya ulinzi na usalama ambavyo ni JESHI LA UKOMBOZI (JLU), Idara ya Usalama wa Zanzibar na kuimarisha Jeshi la Polisi.
Kikosi cha Wanamaji Zanzibar (Zanzibar Navy) ambacho asili yake ni Idara ya Usalama Zanzibar kilikuwa na malengo ambayo ni kulinda uhuru wa Zanzibar (ambao ulipatikana kwa mapinduzi ya 1964) pamoja na mipaka ya baharini ya Zanzibar na watu wake.
Mnamo tarehe 01/07/1973 Kikosi cha Wanamaji Zanzibar kubadilishwa jina na kuitwa Kikosi Maalum cha Kuzuia Magendo (KMKM), mbali ya kubadilishwa jina lakini malengo na madhumuni yake yalibaki kuwa yale yale.
Mwaka 1984 Kikosi cha Wanamaji Zanzibar (Zanzibar Navy) kiliondolewa kutoka Idara ya Usalama Zanzibar na kuwa kikosi kinachojitegemea. Kwa mujibu wa Katiba ya Zanzibar ya 1984 inaeleza kuwa Rais wa Zanzibar na Mwenyekiti wa Baraza la Mapinduzi ndiye Kamanda Mkuu wa kikosi hicho na vyengine vilivyoundwa na vitakavyoundwa na Serikali ya Mapinduzi ya Zanzibar.