As the competition in the Taiwanese medical industry becomes increasingly fierce, public hospitals are confronted with challenges in orientation and operations. This study measured changes in the operational efficiency of public and their competitors, non-public hospitals, in Taiwan. This study considered differences in technology and scale between public and non-public hospitals and adopted the quality-incorporating metafrontier Malmquist productivity index to analyze inputs, outputs, and quality achievements of hospitals. The data consisted of 40 public hospitals and 79 non-public hospitals in Taiwan during the period 2008–2014. This study measured productivity growth and quality changes. Moreover, it further identified technological gaps and quality gaps in different types of hospitals with respect to the metafrontier. At the same time, comparisons of changes in quality between public and non-public hospitals were also examined. The empirical results showed that public hospitals were better than non-public ones in terms of productivity. Meanwhile, it was also found that most of the decomposition in productivity was higher in public hospitals than in non-public ones, especially in terms of improvements in technology and quality. This paper presented public hospitals outperformed non-public ones during the research period in spite of the fact that private hospitals had become larger and group-oriented. Therefore, public hospitals and regulators made appropriate adjustments and responses in the face of the pressure of competition in the market.