Service Registries form a core component of Services Computing. They have been successful in enabling loose coupling among services by storing, managing and exposing interface descriptions of available services in a standard description language. However, existing service registries fall short of fulfilling the promise of enabling automatic service discovery and invocation and usually are tied to a particular web service technology. We present RegSOP that uses a novel approach of utilizing behavioral descriptions of available services as the basis for registering and discovering services. Behavioral descriptions can be classified and made available to the programmer at development time without committing to any particular service instance or underlying web service technology. Further, RegSOP computes different relationships among service behavior and automatically builds an ontology of service behavior. RegSOP, therefore, reduces the discovery process at runtime to a quick lookup of service classname. We present the design and implementation of RegSOP and report our evaluation of its capabilities. © 2012 IEEE.