A routing service provides functionality for selecting an instance of a tenant service for processing a service request and for providing the network location of the selected instance to a service client. The service client may utilize the network location to make a service request to the selected instance of the tenant service. The routing service might also route the service request to the selected instance of a tenant service. The selection of a particular instance of a tenant service for processing a service request may be made based upon various factors including, but not limited to, attributes of the service client making the request and/or attributes of instances of the tenant service being called. The selection of an instance of a tenant service might also be made to implement segmentation, to implement A/B testing, to load balance service requests, and/or to gradually deploy new versions of a tenant service.