The Internet of Things (IoT) interconnects physical objects including sensors, vehicles, and buildings into a virtual circumstance, resulting in the increasing integration of Cyber-physical objects. The Fog computing paradigm extends both computation and storage services in Cloud computing environment to the network edge. Typically, IoT services comprise of a set of software components running over different locations connected through datacenter or wireless sensor networks. It is significantly important and cost-effective to orchestrate and deploy a group of microservices onto Fog appliances such as edge devices or Cloud servers for the formation of such IoT services. In this chapter, we discuss the challenges of realizing Fog orchestration for IoT services, and present a software-defined orchestration architecture and simulation solutions to intelligently compose and orchestrate thousands of heterogeneous Fog appliances. The resource provisioning, component placement and runtime QoS control in the orchestration procedure can harness workload dynamicity, network uncertainty and security demands whilst considering different applications’ requirement and appliances’ capabilities. Our practical experiences show that the proposed parallelized orchestrator can reduce the execution time by 50% with at least 30% higher orchestration quality. We believe that our solution plays an important role in the current Fog ecosystem.