UDDI is not capable of handling semantic markups for Web services due to its flat data model and limited search capabilities. The present invention provides semantic service description and matchmaking with registries that conforms to UDDI specification. Specifically, the present invention stores complex semantic markups in UDDI data model and uses that information to perform semantic query processing. The present invention does not require any modification to the existing UDDI registries. The add-on modules reside only on clients who wish to take advantage of semantic capabilities. This approach is completely backward compatible and can integrate seamlessly into existing UDDI infrastructure.