As human lifespan increases and the need for elderly care grows, the demand for healthcare services and its associated costs have surged, causing a decline in the operational efficiency of universal healthcare. This has created an imbalance in medical services across different regions, posing a long-standing challenge for the public. To address this issue, strategies to enhance the capacity, efficiency, and quality of healthcare services in various regions must be developed. The appropriate allocation of medical resources is a fundamental requirement for countries to establish a robust healthcare system. This empirical study utilized data envelopment analysis (DEA) to evaluate the efficiency of medical service capacity and identify potential improvement strategies for counties and cities in Taiwan during the period from 2015 to 2020. The results of this study show that (1) the annual average efficiency of medical service capacity in Taiwan is approximately 90%, indicating that there is still room for a 10% improvement; (2) among the six municipalities, only Taipei City has sufficient healthcare capacity, whereas the efficiency of the remaining municipalities needs improvement; and (3) most counties and cities demonstrated increasing returns to scale, indicating a need to scale up the capacity of medical services as appropriate. Based on the findings of this study, it is recommended that medical personnel be increased accordingly to balance the workload, a favorable working environment be provided to stabilize the medical workforce, and urban–rural medical disparities be balanced to improve service quality and reduce cross-regional health services. These recommendations are expected to provide a reference for society as a whole to promote and enhance public health policies, leading to a continual improvement of the quality of medical services.