TQM is a term associated mainly with ensuring the quality of production, where the emphasis is on quality in all parts of the production process. The introduction of TQM into the operation of a service company therefore seems to be more difficult. In the presented article we address the basic requirements for the introduction of TQM in a company providing road freight transport. The basic PDCA approach needs to be implemented in all processes of the actors involved in the supply chain. The article points out the fact that evaluating the quality of the provided service only on the basis of a single indicator, which is the monitoring of the number of complaints and claims, is not sufficient as evidence of the established TQM system. The customer requires evidence of long-term and serious monitoring. As part of this monitoring, it proposes the creation of an effective evaluation system for evaluating the quality of the external service provider. To determine the priority requirements of the customer, it is appropriate to apply several known simple evaluation methods. In the article, we applied the pairwise comparison method and the Saaty’s method to determine the order of importance of the quality criteria that we previously found in the customer survey: integrity of the consignment, compliance with the agreed delivery time and completeness of the shipment, including documents. We therefore recommend focusing on these criteria when providing TQM in the company.