To support m-commerce applications, a service discovery mechanism where services can announce their presence and mobile users can locate these services is needed. Service discovery in dynamic mobile environments poses many challenges such as service providers may create and delete services or servers anytime; mobile services may be deployed in various forms, etc. In this paper, we propose a design for a Service Locating Service (SLS), which addresses some of these issues to provide a flexible service discovery mechanism for m-commerce applications. In our architecture, we adopt a dynamic tree structure for organizing SLS servers to meet the dynamic requirements of services and servers; we introduce service aggregation for fast locating; and we also propose multiple service matching mechanisms, which contain an attribute matching engine and a semantic matching engine for different service interfaces. We describe our concepts, architecture and implementation, and present a performance study for our prototype.