A method of maintaining multiple firewalls on multiple host nodes. Each host node runs one or more virtual machines. For at least a first host node, the method maintains multiple sets of policies for multiple virtual machines that run on the first host node. The method, upon detecting that a particular virtual machine has been moved from the first host node to a second host node, removes a set of policies associated with the particular virtual machine from the first host node and supplies the set of policies to the second host node.