Objective: To evaluate the effectiveness of a weight loss intervention in Mongolian adults with newly diagnosed type 2 diabetes mellitus and with BMIs ≥ 25.0 kg/m2. Methods: Eighty participants (33 men/47 women) aged 32–56 years old received education sessions to improve nutritional habits and increase physical activity. Participants were counselled in-person on two occasions with regular follow-up by phone to eat less (reduce calorie intake by 30–40% and consume fewer fatty foods), shift food intake to earlier in a day and increase physical activity such as walking, jogging, running and biking. Measurements were performed before and after the 6-month intervention. Results: After 6 months, the average weight loss was 4.3 ± 4.7 kg, representing a 4.9 ± 5.4% reduction in body weight (p < 0.0001). Mean HbA1c decreased from 8.5 ± 2.7% to 6.0 ± 1.8% (p < 0.0001), and the percent of individuals with HbA1c in the diabetic range dropped from 76.3% to 27.5%. These changes were accompanied by marked improvements in cardiovascular risk factors, including total cholesterol (3.92 ± 1.02 to 3.13 ± 0.80 mmol/l; p < 0.0001) and triglycerides (2.11 ± 0.82 to 1.54 ± 0.51 mmol/l; p < 0.0001), and modest reductions in systolic and diastolic blood pressure (p < 0.05). Conclusion: The remarkable improvement in glycemic control and lipid profile in participants suggests that a lifestyle modification intervention targeting weight loss may be highly effective for early diabetes treatment and prevention in Mongolians.