A method for balancing load among firewall security devices (FSDs) is provided. According to one embodiment, imminent shutdown of a first cluster unit of an HA cluster of FSDs is gracefully handled by a switching device. A load balancing (LB) table, forming associations between hash values output by the LB function and corresponding ports of the switching device to which the cluster units are coupled, is maintained. The first cluster unit is coupled to a first port. Responsive to imminent shutdown of the first cluster unit: (i) a second cluster unit, coupled to a second port, is selected to perform security services on traffic sessions handled by the first cluster unit; and (ii) the LB table is updated by replacing reference(s) to the first port with reference(s) to the second port. Security services for subsequently received network traffic associated with the traffic sessions is performed by the second cluster unit.