Multi-state models have been widely used to analyze longitudinal event history data obtained in medical and epidemiological studies. The tools and methods developed recently in this area require completely observed data. However, missing data within variables of interest is very common in practice, and it has been an issue in applications. We propose a type of EM algorithm, which handles missingness within multiple binary covariates efficiently, for multi-state model applications. Simulation studies show that the EM algorithm performs well for both missing completely at random (MCAR) and missing at random (MAR) covariate data. We apply the method to a longitudinal aging and cognition study dataset, the Klamath Exceptional Aging Project (KEAP), whose data were collected at Oregon Health & Science University and integrated into the Statistical Models of Aging and Risk of Transition (SMART) database at the University of Kentucky.