Middle East Respiratory Syndrome Coronavirus (MERS-CoV) likely originated in bats and passed to humans through dromedary camels; however, the genetic mechanisms underlying cross-species adaptation remain poorly understood. Variation in the host receptor, dipeptidyl peptidase 4 (DPP4), can block the interaction with the MERS-CoV spike protein and form a species barrier to infection. To better understand the species adaptability of MERS-CoV, we identified a suboptimal species-derived variant of DPP4 to study viral adaption. Passaging virus on cells expressing this DPP4 variant led to accumulation of mutations in the viral spike which increased replication. Parallel passages revealed distinct paths of viral adaptation to the same DPP4 variant. Structural analysis and functional assays showed that these mutations enhanced viral entry with suboptimal DPP4 by altering the surface charge of spike. These findings demonstrate that MERS-CoV spike can utilize multiple paths to rapidly adapt to novel species variation in DPP4.