Various ways are carried out by each agency to win the trust of the public, among others, by increasing customer satisfaction. One of the government agencies that is committed to increasing customer satisfaction is the Regional Office of the Ministry of Religion of Central Java Province. This study aims to measure the suitability of service quality and recommend alignment of the gap between public perception and management perception which is then used as material for evaluating service quality at the Regional Office of the Ministry of Religion of Central Java Province using Decision Tree with the ID3 algorithm. Attributes of customer satisfaction input in this study using Servqual, including tangibility, reliability, responsiveness, assurance and empathy. In this study, it was found that there is a gap between the perception of service users and the perception of management. Where the improvement of service quality that must be prioritized is the assurance attribute. This research is expected to assist the management in finding the weaknesses of their services and increase customer satisfaction to maintain and increase public trust in government agencies