Malacca Strait has become one prone International shipping lanes to maritime securitythreats, particularly the armed robbery. Littoral States such as Indonesia, Malaysia andSingapore have the capability to guarantee the safety and security of the strait. Thisresearch aims to analyse cooperation between Littoral States in combating armed robberyin the Malacca Strait. Using Neoliberal Institutionalist theory and qualitative method alongwith descriptive approach through interview and library research, this research shows thatsince the initiative of coordinated patrols conducted between the Littoral States there was asignificant decrease in number of attack in armed robbery in the Malacca Strait from 2008to 2010. In addition, several maritime regimes such as The Regional CooperationAgreement on Combating Piracy and Armed Robbery against Ships in Asia (ReCAAP)and The Regional Maritime Security Initiative (RMSI) serve as facilitator to enhance thecooperative mechanism between Littoral States to combat armed robbery in the territory.