Since Winter Road Maintenance (WRM) is an important activity in Nordic countries, accurate intelligent cost-effective WRM can create precise advance plans for developing decision support systems to improve traffic safety on the roads, while reducing cost and negative environmental impacts. Lack of comprehensive knowledge and inaccurate WRM information would lead to a certain loss of WRM budget, safety reduction, and irreparable environmental damage. This study proposes an intelligent methodology that uses data envelopment analysis and machine learning techniques. In the proposed methodology, WRM efficiency is calculated by data envelopment analysis for different decision-making units (roads), and inefficient units need to be considered for further assessments. Therefore, road surface temperature is predicted by means of machine learning methods, in order to achieve efficient and effective WRM on the roads during winter in cold regions. In total, four different methods have been used to predict road surface temperature on an inefficient road. One of these is linear regression, which is a classical statistical regression technique (ordinary least square regression); the other three methods are machine-learning techniques, including support vector regression, multilayer perceptron artificial neural network, and random forest regression. Graphical and numerical results indicate that support vector regression is the most accurate method.