A method for a network controller for configuring a logical network that comprises a distributed middlebox across a plurality of hosts (Host1-Host6), the method comprising: configuring a first middlebox instance executing on a first host (Host2) of the plurality of hosts (Host1-Host6) to: (i) implement the distributed middlebox by load balancing packets sent from a first virtual machine executing on the first host and that have a destination address of a set of servers across the set of servers (ServerVM1-4) and performing destination network address translation (DNAT) for said packets; (ii) obtain health status data for the set of servers (ServerVM1-4) executing on different hosts (Host4, Host5, Host6) of the plurality of hosts (Host1-Host6) to determine whether each server of the set of servers is currently operating; and (iii) disseminate the obtained health status data to a second middlebox instance executing on a second host (Host3) of the plurality of hosts (Hostl-Host6), wherein the distributed middlebox is for providing DNAT and load balancing service to the logical network that comprises a set of logical forwarding elements (115, LogicalSwitch1-3) that connect a plurality of machines (ClientVM1, ClientVM2, ServerVM1-4) including the set of servers, the logical forwarding elements (115, LogicalSwitch1-3) implemented in a distributed manner by a plurality of managed forwarding elements executing on a set of hosts (Host1-Host6) including the first and second hosts; and configuring the second middlebox instance to implement the distributed middlebox by using the health status data received from the first middlebox instance to load balance packets sent from a second virtual machine (ClientVM2) executing on the second host (Host3) and that have the destination address of the set of servers across the set of servers and perform DNAT for said packets, wherein the first and second middlebox instances (140, 145) are among a plurality of middlebox instances (135, 140, 145) that execute on the plurality of hosts to implement the distributed middlebox in a distributed manner across the plurality of hosts (Host1, Host2, Host3). configuring a first middlebox instance executing on a first host (Host2) of the plurality of hosts (Host1-Host6) to: (i) implement the distributed middlebox by load balancing packets sent from a first virtual machine executing on the first host and that have a destination address of a set of servers across the set of servers (ServerVM1-4) and performing destination network address translation (DNAT) for said packets; (ii) obtain health status data for the set of servers (ServerVM1-4) executing on different hosts (Host4, Host5, Host6) of the plurality of hosts (Host1-Host6) to determine whether each server of the set of servers is currently operating; and (iii) disseminate the obtained health status data to a second middlebox instance executing on a second host (Host3) of the plurality of hosts (Hostl-Host6), (i) implement the distributed middlebox by load balancing packets sent from a first virtual machine executing on the first host and that have a destination address of a set of servers across the set of servers (ServerVM1-4) and performing destination network address translation (DNAT) for said packets; (ii) obtain health status data for the set of servers (ServerVM1-4) executing on different hosts (Host4, Host5, Host6) of the plurality of hosts (Host1-Host6) to determine whether each server of the set of servers is currently operating; and (iii) disseminate the obtained health status data to a second middlebox instance executing on a second host (Host3) of the plurality of hosts (Hostl-Host6), wherein the distributed middlebox is for providing DNAT and load balancing service to the logical network that comprises a set of logical forwarding elements (115, LogicalSwitch1-3) that connect a plurality of machines (ClientVM1, ClientVM2, ServerVM1-4) including the set of servers, the logical forwarding elements (115, LogicalSwitch1-3) implemented in a distributed manner by a plurality of managed forwarding elements executing on a set of hosts (Host1-Host6) including the first and second hosts; and configuring the second middlebox instance to implement the distributed middlebox by using the health status data received from the first middlebox instance to load balance packets sent from a second virtual machine (ClientVM2) executing on the second host (Host3) and that have the destination address of the set of servers across the set of servers and perform DNAT for said packets, wherein the first and second middlebox instances (140, 145) are among a plurality of middlebox instances (135, 140, 145) that execute on the plurality of hosts to implement the distributed middlebox in a distributed manner across the plurality of hosts (Host1, Host2, Host3).