In this paper, we present a novel semantics for an essential aspect of service-oriented computing: the mechanism through which systems evolve through a symbiosis of state transformations and run-time service discovery and binding. The semantics is based on a new notion of temporal symbolic graph-transformation systems: in temporal symbolic graphs, interfaces can be specified using temporal logic, and service-level agreements can be specified in that logic's propositional fragment. An important advantage of our framework is that it can be supported by tools that implement temporal symbolic graph transformations, which would also provide a means of animating service-oriented systems evolution. We illustrate our semantics with a simple trip-booking service.