Complex activities typically consist of multiple primitive events happening in parallel or sequentially over a period of time. Understanding such activities requires recognizing not only each individual event but, more importantly, capturing their spatiotemporal dependencies over different time intervals. Most of current graphical model-based approaches have several limitations. First, time-sliced graphical models such as Hidden Markov Models (HMMs) and Dynamic Bayesian Networks are typically based on points of time and they hence can only capture three temporal relations: precedes, follows, and equals. Second, HMMs are probabilistic finite-state machine that grow exponentially as the number of parallel events increases. Third, other approaches such as syntactic and description-based methods, while rich in modeling temporal relationships, do not have the expressive power to capture uncertainties. To address these issues, we introduce the Interval Temporal Bayesian Network (ITBN), a novel graphical model that combines the Bayesian Network with the Interval Algebra (IA) to explicitly model the temporal dependencies over time intervals. Advanced machine learning methods are introduced to learn the ITBN model structure and parameters. Experimental results show that by reasoning with spatiotemporal dependencies the proposed model leads to a significantly improved performance when modeling and recognizing complex activities involving both parallel and sequential events.