A multitude of issues affect the broader adoption of Cloud computing, with security arguably being amongst the most significant. To address security concerns, the process of threat analysis is advocated to assess potential attacks that can undermine the security goals. However, conducting threat analysis for the Cloud is a non-Trivial task given the plethora of attack surfaces entailed in the multiple layers of the operational stack and the resource/customer interfaces. Consequently, contemporary Cloud threat analyses approaches primarily focus on specific services/layers without analyzing the malicious behaviors over the complete multi-layered Cloud ecosystem. Hence, the need is of a comprehensive Cloud threat analysis approach that can (a) analyze the spectrum of malicious behaviors stemming from the vulnerable service interactions across the multi-level operational stack, and (b) correspondingly enumerate the attack surface exploitability by varied types of attackers. We achieve such a holistic Cloud threat analysis via a novel multi-level modeling of Cloud operations to obtain a comprehensive behavioral profile of its underlying services. Our proposed approach, using Petri Nets, targets the identification of core operational states to enumerate the normal sequence of Cloud operations along with the triggers that provide the state transitions. The obtained states transition enumerate comprehensive multi-level state space baseline of 'normal' sequences and also constitutes to identify multi-level vulnerabilities not recognizable by the traditional single-level threat analysis. © 2017 IEEE.