AbstractNetwork function virtualization (NFV) enables on‐demand network function (NF) deployment providing agile and dynamic network services. Through an evaluation metric that quantifies the minimal reliability among all NFs for all demands, service providers and operators may better facilitate flexible NF service recovery and migration, thus offering higher service reliability. In this paper, we present evaluation metrics on NFV reliability and solution approaches to solve robust NFV under random NF‐enabled node failure(s). We demonstrate how to construct an auxiliary NF‐enabled network and its mapping onto the physical substrate network. With the constructed NF‐enabled network, we develop pseudo‐polynomial algorithms to solve the robust NF and SFC s − t path problems: subproblems of robust NFV. We also present approximation algorithms for robust NFV with the SFC‐Fork as the NF forwarding graph. Furthermore, we propose exact solution approaches via mixed‐integer linear programming under the general setting. Computational results show that our proposed solution approaches are capable of managing robust NFV in a large‐size network.