The optimal placement of virtual network functions (VNFs) improves the overall performance of servicefunction chains (SFCs) and decreases the operational costs formobile network operators. To cope with changes in demands,VNF instances may be added or removed dynamically, resourceallocations may be adjusted, and servers may be consolidated.To maintain an optimal placement of SFCs when conditionschange, SFC reconfiguration is required, including the migration of VNFs and the rerouting of service-flows. However, suchreconfigurations may lead to stress on the VNF infrastructure,which may cause service degradation. On the other hand, notchanging the placement may lead to suboptimal operation,and servers and links may become congested or underutilized,leading to high operational costs. In this paper, we investigatethe trade-off between the reconfiguration of SFCs and theoptimality of their new placement and service-flow routing. Wedevelop a multi-objective genetic algorithm that explores thePareto front by balancing the optimality of the new placementand the cost to achieve it. Our numerical evaluations show thata small number of reconfigurations can significantly reduce theoperational cost of the VNF infrastructure. In contrast, toomuch reconfiguration may not pay off due to high costs. Webelieve that our work provides an important tool that helpsnetwork providers to plan a good reconfiguration strategy fortheir service chains.