To reduce the time required in developing the web services fault tolerant, researchers have investigated some methods on automating the process of fault diagnosis. Most existing techniques either assume a complete process model or fault types available in the diagnostic system. Moreover, empirical studies have shown that the existing diagnosis methods are not adequate to meet the growing requirements of business processes. In this paper, we propose a Hidden Markov Model (HMM) based diagnosis method for autonomously diagnosing the faults in web service composition process. Our diagnosis method incorporates historical process data into model-based diagnosis for overcoming the limitations of the uncompleted process model and finite historical process data. Our diagnosis result can provide an explanation for the service faults. Moreover, we present an architecture of diagnostic system for simplifying diagnostic process, adding diagnostic capability and guaranteeing the privacy of web services. The experimental results show that our method is effective and robust to various noises in diagnosing the faults of web services.