Network Functions Virtualization (NFV) is transforming the way enterprises deploy, maintain, and evolve their network services. With NFV, enterprises can deploy various network functions such as routers, firewalls, and load balancers as software instances running on commercial off-the-shelf servers. By adopting this new approach, enterprises are increasingly outsourcing their network services to the cloud, ultimately reaping the rewards of cloud computing, which include high availability, lower costs, and theoretically infinite resources.However, many enterprises are reluctant to embrace this new approach, due to a lack of trust in the cloud. Such reluctance stems from the opacity of the cloud, the risk of dishonest behavior by the cloud provider, and the risk of attacks from inside or outside. As a result, enterprises considering outsourcing their network services to the cloud are sorely lacking in assurances that their network services will meet their specifications. Violations of network service specifications are highly detrimental to the business success and image of enterprises, as these violations compromise their security, quality of service, and resiliency objectives. Thus, outsourcing network services to the cloud requires first and foremost establishing trust between enterprises and the cloud.In this thesis, we argue that a systematic verification of network services remains the key to addressing the lack of enterprises’ trust in the cloud. Verification involves confronting the network service state to detect network service anomalies or to assess the compliance of the network service state with its specification. Thus, with verification mechanisms, enterprises can anticipate and detect specification violations, a.k.a. network service anomalies, remediate them, and claim compensation from cloud-NFV providers.This thesis proposes several contributions in the context of verification of outsourced network services to the cloud. First, we present a taxonomy of network service anomalies that can occur in NFV environments. Along with this taxonomy, we analyze the negative impacts of network service anomalies on critical service attributes such as confidentiality, integrity, and performance. As a second contribution, we introduce VeriNeS, a verification system that observes the behavior of the NFV Orchestrator to detect network service anomalies. By intercepting configuration commands issued by the NFV Orchestrator, VeriNeS builds a global state of all network services instead of a single state per network service. With this approach, VeriNeS overcomes cardinal limitations of the NFV architecture that include the lack of details to correlate the state of network services with their respective owners. VeriNeS integrates with the NFV architecture without the need to modify existing components and responds to verification requests in an acceptable time frame for real-world deployment scenarios.