Service-oriented computing is now acknowledged as a central paradigm for Internet computing, supported by tremendous research and technology development over the last 10 years. However, the evolution of the Internet, and in particular, the latest Future Internet vision, challenges the paradigm. Indeed, service-oriented computing has to face the ultra large scale and heterogeneity of the Future Internet, which are orders of magnitude higher than those of today’s service-oriented systems. This article aims at contributing to this objective by identifying the key research directions to be followed in light of the latest state of the art. This article more specifically focuses on research challenges for service-oriented middleware design, therefore, investigating service description, discovery, access, and composition in the Future Internet of services.