Objective: This study examined the change in physical activity status and patterns and their associations with urban and rural residence and employment status in Mongolia.Methods: We analyzed data from 7,738 adults aged from 20 to 64 years (n = 2,877 and 4,861 for 2005 and 2013, respectively) from the Mongolian STEPS Survey on the Prevalence of Non-Communicable Disease Risk Factors (NCD-STEPS survey). Physical activity in three domains, including work (occupational and household work); transport (walk or cycling); and leisure (sport or fitness) was measured by Global Physical Activity Questionnaire (GPAQ). Physical activity levels were classified into three groups: low, moderate, and high according to the GPAQ analysis framework. The associations between physical activity time, residential area, and employment status were examined using a multivariate negative binomial regression model.Results: The percentage of respondents with low-level physical activity increased from 10.9% in 2005 to 27.2% in 2013. The median minutes of physical activity time per week were 1,020 in 2005 and 600 in 2013. Physical activity time at work, transport and overall decreased in 2013. Work-related physical activity was the most dominant component of physical activity time (55.6% in 2005 and 54.6% in 2013), the transport domain was the second-highest contributor of physical activity time in 2005 (24.0%) and was replaced by the leisure domain (26.8%) in 2013. Rural residents practiced more physical activity at work, transport, and leisure than urban residents did in 2005 (prevalence ratio [PR]: 1.33, 95% confidence interval [CI]: 1.20–1.47; PR: 1.21, 95%CI: 1.14–1.29; and PR: 1.21, 95%CI: 1.13–1.30, respectively), but there was no significant difference by residential area in 2013. Mongolian adults with higher educational attainment, employee status, and non-employment status were less likely to engage in physical activity compared to those among adults with lower educational attainment and self-employed status.