Propensity score matching (PSM) has been widely used to mitigate confounding in observational studies, although complications arise when the covariates used to estimate the PS are only partially observed. Multiple imputation (MI) is a potential solution for handling missing covariates in the estimation of the PS. Unfortunately, it is not clear how to best apply MI strategies in the context of PSM. We conducted a simulation study to compare the performances of popular non-MI missing data methods and various MI-based strategies under different missing data mechanisms (MDMs). We found that commonly applied missing data methods resulted in biased and inefficient estimates, and we observed large variation in performance across MI-based strategies. Based on our findings, we recommend 1) deriving the PS after applying MI (referred to as MI-derPassive); 2) conducting PSM within each imputed data set followed by averaging the treatment effects to arrive at one summarized finding (INT-within) for mild MDMs and averaging the PSs across multiply imputed datasets before obtaining one treatment effect using PSM (INT-across) for more complex MDMs; 3) a bootstrapped-based variance to account for uncertainty of PS estimation, matching, and imputation; and 4) inclusion of key auxiliary variables in the imputation model.