Systems and methods are disclosed to implement a request routing layer of a service provider system, where the request routers are aware of different versions of a service implemented by the servers of the system. In embodiments, the request routers may discover the different versions of the service via periodic health messages or request responses from the servers. Requests are routed to the servers according to a routing policy that specifies the relative proportions of requests that are to be routed to each version. Version metrics generated from the requests may be captured and provided to a version change manager, which may update the routing policy based on the metrics, either increasing or decreasing the proportion of requests for the different versions. In embodiments, the request router may implement additional rules that control their routing behavior in response to detected error conditions.