Change orders in construction projects are very common and result in negative impacts on various project facets. The impact of change orders on labor productivity is particularly difficult to quantify. Traditional approaches are inadequate to calculate the complex input-output relationship necessary to measure the effect of change orders. This study develops the Evolutionary Fuzzy Support Vector Machines Inference Model (EFSIM) to more accurately predict change-order-related productivity losses. The EFSIM is an AI-based tool that combines fuzzy logic (FL), support vector machine (SVM), and fast messy genetic algorithm (fmGA). The SVM is utilized as a supervised learning technique to solve classification and regression problems; the FL is used to quantify vagueness and uncertainty; and the fmGA is applied to optimize model parameters. A case study is presented to demonstrate and validate EFSIM performance. Simulation results and our validation against previous studies demonstrate that the EFSIM predicts the impact of change orders significantly better than other AI-based tools including the artificial neural network (ANN), support vector machine (SVM), and evolutionary support vector machine inference model (ESIM).