Malacca strait is one of the important international trade route and because of its strategic location it has very crowded and congested traffic and vulnerable to various crime such as maritime piracy, illegal trafficking, terrorism, and human trafficking. As littoral states, Indonesia, Malaysia, and Singapore are responsible for the security of the strait, their effort for creating form of integration cooperation between them to creat a maritime navigational safety in the strait. This research focuses on how their efforts and types of cooperation they do regarding strait issues and Due to the involvement of a lot of interest in the waterway either from littoral states or the user states. This is a qualitative research and supported by theories and also secondary data so that in this study will obtained proff and truth of the fundings. To adapt with variety of growing crime in Malacca Strait, the integration between the three coastal states also continues to evolve from the only form of cooperation agreements and committees, to practical cooperation such as patrol coordination like operation MALSINDO, Initiatives Eye in the Sky and billateral security cooperation as Military Training Area (MTA) and Defence Cooperation Agreement (DTA). The results of this study explains the drop in crime in the waterway each year (2004-2010) resulting from the integration of these three coastal State as the basis of cooperation agreements techinical Tripartite Experts Group (TTEG) which later results forward and more deep cooperation mechanism (CF) involving not only three coastal states but whoever has interest in waterway to create a maritime navigational safety in Malacca Strait.