The Surabaya City E-Health service is one of the digital public services used for online queue registration for community health centers and hospitals owned by the Surabaya City government. Over the past three years, the number of individuals using the service has risen, but during implementation, service users still face several obstacles. The obstacles users encounter certainly affect their experience using the service. Therefore, it is important to evaluate the quality of Surabaya City's E-Health service using the E-GovQual and Importance-Performance Analysis (IPA) methods. Data collection was conducted using questionnaires distributed to users, and 400 respondents who met the research sample criteria were obtained. The analysis using E-GovQual found the lowest gap level for the RL6 indicator at -0.17 and the highest level of conformity at 96%. The quadrant mapping results on the IPA diagram identified six indicators that were highlighted for improvement: TR1, TR2, TR3, TR4, RL2, and CS2. Several improvement recommendations were provided in accordance with the priority improvement indicators, including those related to the security of service users' personal data. In contrast to earlier E-GovQual–IPA research that mainly evaluates general e-government portals, this study delivers an in-depth assessment of a municipal public healthcare digital service and presents targeted strategic suggestions derived from quadrant prioritization. The results emphasize the essential importance of trust-related factors, especially data protection and system dependability, in enhancing public trust in local e-health services