This study aims to analyze barriers and formulate strategies to accelerate the accreditation of the Nunukan Regency Transportation Agency's Motor Vehicle Inspection Technical Implementation Unit (UPT PKB). Accreditation is a requirement of the Ministry of Transportation to ensure service quality, safety, and compliance with national standards. To date, the Nunukan Regency UPT PKB has not yet obtained accreditation, resulting in weak formal legitimacy and poor quality of public services in the motor vehicle inspection sector. This study used a qualitative method based on case studies. Data were collected through in-depth interviews and field observations, and then analyzed using the Miles & Huberman interactive model. The analysis focused on the application of the “Plan-Do-Check-Act” (PDCA) framework, integrated with Total Quality Management (TQM) principles, to identify barriers and develop continuous improvement strategies. The results indicate that barriers to accelerating accreditation stem from three main categories. Internal factors include limited human resources, substandard facilities and infrastructure, and incomplete quality documentation. External factors include budgetary constraints, difficult geographical conditions, weak inter-institutional coordination, and the absence of regional regulations. Structural and bureaucratic factors include weak synergy between DPOs and a lack of urgency regarding the accreditation process.