Recent advances in wireless and mobile networking technology pose a new set of requirements and challenges that are not previously thought of, when it comes to smart space middleware design. Leading the list is how to embrace diversity and unpredictability inherent in mobile computing environments. Service-oriented computing is being recognized as one of viable solutions to the problem. According to the paradigm, dynamic service discovery and composition should be able to handle the dynamism and diversity in the environments. However, most current service frameworks do not provide sufficient support to mask the complexity from having to deal with the uncertainty by ourselves. Therefore, building an application via qualified service composition still remains a cumbersome and daunting task. In this paper, we present a smart space middleware architecture designed to hide the complexity involved with context-aware, automated service composition. We also report our prototype implementations as an effort to validate the effectiveness and feasibility of the architecture. © Springer-Verlag Berlin Heidelberg 2007.