Methods, systems, and computer readable media for providing a workload balancer for balancing message traffic received over long-lived Diameter connections are disclosed. One exemplary workload balancer includes at least one connection front end processor for terminating Diameter connections with external nodes. The workload balancer further includes a plurality of Diameter back end processors for performing application or routing processing for the Diameter messages received over the Diameter connections. The at least one connection front end processor load shares Diameter messages received over existing Diameter connections among the back end processors.