One goal of disease progression modeling is to infer biomarker trajectories in patients as the disease unfolds. Mapping the disease trajectory is critical in early diagnosis, patient staging, and clinical trial design. However, accurately capturing biomarker trajectories over time is challenging due to limited longitudinal data and substantial inter-individual variability. Discrete disease progression models were developed to overcome these challenges by using cross-sectional or short-term longitudinal data to map disease progression. These models often view disease progression as a latent permutation of events, using maximum likelihood estimation to predict event sequence. Using these models can be restrictive due to their combinatorial growth in runtime and vulnerability to noise, making them infeasible to use on high-dimensional or noisy data. Here, we introduce FastEBM which leverages manifold learning and Markov chains to model disease progression as a subject-level ordering along the disease continuum, enabling us to achieve fast and noise-robust event sequence estimation. Using this approach we were able to achieve 3,500 times faster inference compared to the state-of-the-art models while maintaining high accuracy. Using simulated data, FastEBM outperforms other existing EBM models by up to 80% in terms of accuracy in high-dimensional noisy settings. Furthermore, when applied to real-world data from the Alzheimer’s Disease Neuroimaging Initiative, only FastEBM revealed a sequence of disease progression that aligns with established clinical understanding and literature: increased amyloid- \(\beta \) levels preceded tau accumulation, which were followed by structural brain atrophy and subsequently, cognitive decline. Overall, FastEBM provides an efficient, interpretable, and accurate way to model disease progression that can be applied to data from different modalities with potential for clinical application.