The techniques describe effective detection of latency-related issues for a cloud service operating in a distributed computing environment. To detect the latency-related issues, a system first determines baseline latency behavior at the tenant level (e.g., on a tenant-by-tenant basis) and compares a tenant's current latency behavior to the baseline latency behavior. If the comparison yields that the current latency behavior for the tenant is following the baseline latency behavior, the tenant is deemed healthy. However, if the comparison yields that the current latency behavior for the tenant is not closely following the baseline latency behavior, the tenant is deemed unhealthy. Once the system has made binary health determinations for various tenants on a tenant-by-tenant basis, the system is configured to aggregate the unhealthy determinations across a group of tenants to determine whether the cloud service is experiencing latency-related issues.