Network Function Virtualization (NFV) holds a great promise as it provides flexibility and scalability, reduces costs, and promotes innovation (by moving from hardware-based middleboxes to software-based virtual network functions). These benefits, however, expose network functions to security vulnerabilities. In this paper, we investigate two such attack vectors: algorithmic complexity Denial of Service (DoS) attacks and attacks due to co-residency, which include side-channel attacks and DoS attacks on a specific machine. We propose Moving Target Defense (MTD) mechanisms—which force an attacker to cope with frequent changes ongoing within the targeted network function to carry out a successful attack through the above-mentioned attack vectors. For algorithmic complexity DoS attacks, we show a mechanism that proactively and reactively switches between different implementations of the network function. Thus, eliminating the certainty of the attacker regarding the targeted implementation. For co-residency attacks, we show a framework to efficiently migrate the virtual network function state without migrating the entire virtual machine, which is prohibitive in such a challenging setting. Our experiments show that both mechanisms can counteract these attack vectors and provide significantly better performance than state-of-the-art solutions.