Combustion instability poses a negative impact on the performance and structural durability of both land-based and aircraft gas turbine engines, and early detection of combustion instabilities is of paramount importance not only for performance monitoring and fault diagnosis, but also for initiating efficient decision and control of such engines. Combustion instability is, in general, characterized by self-sustained growth of large-amplitude pressure tones that are caused by a positive feedback arising from complex coupling of localized hydrodynamic perturbations, heat energy release, and acoustics of the combustor. This paper proposes a fast dynamic data-driven method for detecting early onsets of thermo-acoustic instabilities, where the underlying algorithms are built upon the concepts of symbolic time series analysis (STSA) via generalization of D-Markov machine construction. The proposed method captures the spatiotemporal co-dependence among time series from heterogeneous sensors (e.g. pressure and chemiluminescence) to generate an information-theoretic precursor, which is uniformly applicable across multiple operating regimes of the combustion process. The proposed method is experimentally validated on the time-series data, generated from a laboratory-scale swirl-stabilized combustor, while inducing thermo-acoustic instabilities for various protocols (e.g. increasing Reynolds number (Re) at a constant fuel flow rate and reducing equivalence ratio at a constant air flow rate) at varying air-fuel premixing levels. The underlying algorithms are developed based on D-Markov entropy rates, and the resulting instability precursor measure is rigorously compared with the state-of-the-art techniques in terms of its performance of instability prediction, computational complexity, and robustness to sensor noise. © 2016, © The Author(s) 2016.