Network function virtualization (NFV) and Service function chaining (SFC) can fulfill the traditional network functions by simply running special softwares on general‐purpose computer servers and switches. This not only provides significantly more agility and flexibility in network service deployment, but can also greatly reduce the capital and operating cost of networks. In this paper, a comprehensive survey on the motivations and state of the art efforts towards implementing the NFV and SFC is provided. In particular, the paper first presents the main concepts of these new emerging technologies; then discusses in details various stages of SFC, including the description, composition, placement and scheduling of service chains. Afterwards, existing approaches to SFC are reviewed according to their application environments, parameters used, and solution strategies. Finally, the paper points out a number of future research directions.