This paper describes our experience with the use of Universal Description, Discovery and Integration (UDDI) technology for supporting location-based service discovery. Our goal is to allow Web Services to be associated with physical locations and then queried according to spatial criteria. This would enable location-based applications to use local UDDI registries todiscover the Web Services that are relevant for the current location of a mobile user. However, the current model for Web Services discovery in UDDI does not directly support the particular requirements of location-based discovery. The main limitation is the inadequacy of the query-processing mechanism, based on exact matching between query criteria and servicecategorizations, to support discovery models based on proximity. We propose an approach that includes a space model that allows external entities to obtain information about the spatial structure of the local environment, a set of querying taxonomies that allow UDDI queries to include spatial criteria while maintaining conformance with the UDDI standards, and a proxy that allows application to benefit from spatial queries while maintaining the approach transparent. This approach iscurrently being used and evaluated in the VADE project.