To realize hybrid Web service composition when Web Services Description Language (WSDL) and Web Ontology Language for Service (OWL-S) coexist, an approach based on interface automata was presented. Firstly, the interface automata were employed to accomplish automatic recognition and composition of Web services after analyzing the relations between WSDL and OWL-S. Simultaneously, the optimal results were obtained to realize different service business logic by comparing the service composition with the predefined service quality. The results of a tourism service sample show that the approach is feasible and effective, and the efficiency of service composition is improved by 5%-10%.