Concepts and technologies are disclosed herein for a distributed stateful load balancer. A first load balancer can store a first portion of a distributed hash table including data over a first range of hash keys. The first load balancer can be in communication with a second load balancer that stores a second portion of the distributed hash table including data over a second range of hash keys. The first load balancer can receive a packet, where a hash value calculated for the packet does not fall in the first range of hash keys. The first load balancer can identify, based on the hash value, that the second load balancer stores data that identifies a path associated with the packet and query the second load balancer to identify the path. The first load balancer can receive the data and forward, along the path, the packet to a network element.