Microservice architectures have gained enormous popularity due to their ability to be dynamically added/removed, replicated, and updated according to run-time needs. However, the dynamic nature of microservices introduces uncertainty, which in turn can affect the provided Quality of Service (QoS). This calls for novel service discovery mechanisms able to adapt to the variability of the QoS attributes and further perform effective service discovery and selection. To this end, this paper combines machine learning and self-adaptation techniques to perform service discovery and selection by trading off different QoS attributes. The results of our validation on a state-of-the-art microservices exemplar show that our ML-enabled approach can perform service discovery with 35% higher effectiveness with respect to existing baselines.