A distributed load balancer in which a router receives packets from at least one client and routes packet flows to multiple load balancer (LB) nodes according to a per-flow hashed multipath routing technique. For a given packet flow, the LB nodes randomly select a server node as a target for the packet flow from among multiple server nodes and send a connection request to the server node. A load balancer module on the server node makes the decision on whether to accept or reject the connection based on one or more metrics indicating a respective server's current load. If the module accepts the connection request, a connection is established between the server and the client. Otherwise, the load balancer nodes may select another server node and try again. The connections established between clients and servers pass through the load balancer nodes, but are not terminated at the load balancer nodes.