Pervasive Computing will be a fertile source of challenging research problems in computer systems for many years to come. The ability to obtain services and information from an environment anywhere at anytime is part of pervasive computing. The problem is that most of existing services and applications are designed for stationary PCs. How to evolve these so called legacy system towards those mobile users in a controlled manner is vital for that pervasive computing can become more widespread. In this paper, we report our efforts on the PerEvo project. After discussing the basic features and challenges of pervasive computing, we present an agent-based Web services evolution approach, which is well suited to building software solutions for pervasive computing, and illustrate our solutions through a booking scenario.