The explosive growth of user devices and emerging applications is driving unprecedented traffic demands, accompanied by stringent Quality of Service (QoS) requirements. Addressing these challenges necessitates innovative service orchestration methods capable of seamless integration across the edge-cloud continuum. Terrestrial network-based service orchestration methods struggle to deliver timely responses to growing traffic demands or support users with poor or lack of access to terrestrial infrastructure. Exploiting both aerial and terrestrial resources in service composition increases coverage and facilitates the use of full computing and communication potentials. This paper proposes a service placement and composition mechanism for integrated aerial-terrestrial networks over the edge-cloud continuum while considering the dynamic nature of the network. The service function placement and service orchestration are modeled in an optimization framework. Considering the dynamicity, the Aerial Base Station (ABS) trajectory might not be deterministic, and their mobility pattern might not be known as assumed knowledge. Also, service requests can traverse through access nodes due to users' mobility. By incorporating predictive algorithms, including Deep Reinforcement Learning (DRL) approaches, the proposed method predicts ABS locations and service requests. Subsequently, a heuristic isomorphic graph matching approach is proposed to enable efficient, latency-aware service orchestration. Simulation results demonstrate the efficiency of the proposed prediction and service composition schemes in terms of accuracy, cost optimization, scalability, and responsiveness, ensuring timely and reliable service delivery under diverse network conditions.