This paper proposes a hidden state Markov model (HMM) that incorporates workers’ unobserved labor market attachment into the analysis of labor market dynamics. Unlike previous literature, which typically assumes that a worker’s observed labor force status follows a first-order Markov process, the proposed HMM allows workers with the same labor force status to have different history-dependent transition probabilities. I show that the estimated HMM generates labor market transition probabilities that match those observed in the data, while the first-order Markov model (FOM) and its many-state extensions cannot. Even compared with the extended FOM, the HMM improves the fit of the empirical transition probabilities by a factor of 30. I apply the HMM to (1) calculate the long-run consequences of separation from stable employment, (2) study evolutions of employment stability across different demographic groups over the past several decades, (3) compare the dynamics of labor market flows during the Great Recession to those during the 1981 recession, and (4) highlight the importance of looking beyond distributions of current labor force status.