Performing complex tasks over the Web has become an integral part of our everyday life. The advent of mobile services will add to the broad range of existing services offered on the Web and provide additional features like location-based information. To take full advantage of complex service offerings, even on limited client devices, and to handle the growing variety of applications, powerful concepts for personalization are needed. Advanced profiling techniques in combination with semantically enriched service descriptions promise to enable automatic discovery, composition and execution of services. Driven by a usage scenario, this paper proposes a roadmap towards personalization of mobile services.