The objective of this research is to determine the location for the dock and office of naval bases in Padang city of Indonesia. Following this objective, the Regional Government of Padang Mentawai Islands District provides 3 (three) alternative places namely in Semabuk Bay, Siuban Bay, and Semebai Bay for the location of dock and office of Naval Base. For the selection of Mentawai base, the method uses BORDA and PROMETHEE, since the methods can consider alternative evaluation based on factors that are both qualitative and quantitative. Based on the research of BORDA method calculation on 16 naval base selection criteria, it is found that criterion of Sailing Flow maintains the highest weight value that is equal to 10.9% and the lowest criterion weighted value belongs to criterion Political Condition for about 2%. For the results of ranking against the alternative using the Promethee method, the study obtains Semebai Bay as the best location to serve for the location of the base of the Mentawai Naval Base.