At a particular node of a storage service to which connections have been established on behalf of one or more clients, respective workload indicators are collected from a set of peer nodes of the storage service. A determination is made at the particular node that (a) a local workload metric exceeds a connection rebalancing threshold, and (b) a peer capacity availability criterion has been met. The peer capacity availability criterion may be determined from the respective workload indicators. In response to the determination, a particular client connection is closed.