Preconstruction services play a vital role in ensuring timely approval of infrastructure funds and successful execution of construction projects. Most state DOTs use simple methods such as a percentage of estimated construction costs that has proven to be unreliable. Several studies have developed statistical models using historical data to improve current practices. However, such models have performed poorly, and practitioners have not utilized these models. This study develops and evaluates data mining models such as multiple regression and artificial neural networks and concludes that such models do not provide sufficiently accurate estimates of preconstruction service fees and hours. Subsequently, it proposes an alternative approach using a case-based reasoning (CBR) technique that uses similarity scoring to retrieve the most similar projects. The historical preconstruction service fees and hours of similar projects can be used to estimate preconstruction service fees and hours for a new project and make any adjustment necessary. A spreadsheet tool is developed to implement this CBR technique. The tool provides a simple and flexible platform that enables engineers to extract necessary data and help them in making data-driven estimates. Thus, the tool is expected to aid state DOT engineers in negotiating with consultants with higher confidence.