Abstract: This study deals with the problem of tuning metaheuristics for the solution of hard combinatorial optimization problems using machine learning techniques. Decision rules, learned from a corpus of various solutions of randomly generated instances, are repeatedly used to predict solutions quality for a given instance of the combinatorial problem when solved by the metaheuristic. This predicted solution quality is used to fine tune and guide the metaheuristic to more promising search regions during the course of its execution. Results from extensive experimentation on a wide range of hard combinatorial optimization problems ranging from the knapsack problem to the well known Travelling Salesman Problem (TSP) show a noticeable improvement in the objective function value of the solution found by our approach as well as the execution time compared to plain metaheuristics. However, the process of building the corpus and extracting the classification rule is still time consuming but we think it is worth the effort given the fact that this corpus is built only once and also, can provide quick and quality solutions for a stream of instances of the combinatorial problem.