Selecting an optimal logistics service provider is a complex multi-criteria decision-making problem that directly affects a company’s competitiveness. This paper proposes a hybrid MCDM model that integrates the Full Consistency Method (FUCOM) and Measurement Alternatives and Ranking according to Compromise Solution (MARCOS) methods. FUCOM was used to determine the weight coefficients of seven criteria, while MARCOS was applied to rank ten potential logistics providers in the market of Bosnia and Herzegovina. The case study was conducted for the company Hygiene Pro Team from Banja Luka. The results showed that provider P9 represents the most favorable solution, which was confirmed by an extensive sensitivity analysis that verified the stability of the model. The proposed FUCOM–MARCOS model provides a robust framework for strategic decision-making in logistics.