European maritime states are facing increasing challenges that threaten national security, maritime traffic safety, and environmental protection: increasing maritime traffic, increase in nautical tourism, oil spills, migrant boats, drug smuggling, etc. The Coast Guard is one of the most important government agencies to respond to these challenges. However, the speed of response to incidents depends on the geographical and geostrategic deployment of Coast Guard resources, especially of its homeports. The main objective is to have the Coast Guard’s homeports as close as possible to the national border at sea so that the response time to an incident is as fast as possible. However, there are many other criteria that affect the selection of the maritime location of the Coast Guard homeport. These other criteria (security issues, logistic issues, hydrographic and oceanographic features, and similar) are often in conflict with geographical locations on small remote islands that are close to the state border at sea. Therefore, this research analyzed and proposed the criteria set used to assess the maritime locations that could be potential Coast Guard homeports. A large sample of experts has been interviewed to evaluate the proposed criteria set and to propose criteria weights, thus creating the multi-criteria analysis model for the improvement of the spatial distribution of Coast Guard resources. The proposed model is based on the PROMETHEE method and provides evaluation and ranking of the maritime locations in order to help the Government prioritize the development of the maritime locations into the homeports for the deployment of Coast Guard resources. The case study of the eastern Adriatic Sea with real-world maritime locations and data was used to test the proposed model. The results have shown that, with proper strategic planning of the deployment of Coast Guard resources, the sustainability, safety, and security of the sea and the coast can be increased.