The problem we deal with in this paper is the dynamic substitution of stateful services that become unavailable during the execution of service orchestrations. Previous research efforts focusing on the reconfiguration of conventional distributed systems enable the substitution of system entities with other prefabricated passive entities that serve as a backup. Nevertheless, the problem of service substitution is far more complex. In SOA, we can assume the possible existence of several semantically compatible services capable of performing the same or similar tasks. However, each one of them constantly serves requests and cannot be considered as a passive backup for other services. Therefore, we propose the SIROCO middleware platform, enabling the runtime, semantic-based service substitution. The basic concepts of SIROCO are??discussed along with an experimental evaluation of our first prototype. Our findings show that SIROCO provides the necessary means for achieving dynamic service substitution with a reasonable expense on the execution of service orchestrations.