Accurate and reliable effort and cost estimation are still challenging for agile teams in the industry. It is argued that leveraging historical data regarding the actual time spent on similar past projects could be very helpful to support such an activity before companies embark upon a new project. In this paper, we investigate to what extent user story information retrieved from past projects can help developers estimate the effort needed to develop new similar projects. In close collaboration with a software development company, we applied design science and action research principles to develop and evaluate a tool that employs Natural Language Processing (NLP) algorithms to find past similar user stories and retrieve the actual time spent on them. The tool was then used to estimate a real project that was about to start in the company. A focus group with a team of six developers was conducted to evaluate the tool’s efficacy in estimating similar projects. The results of the focus group with the developers revealed that the tool has the potential to complement the existing estimation process and help different interested parties in the company. Our results contribute both towards a new tool-supported approach to help user story estimation based on historical data and with our lessons learned on why, when, and where such a tool and the estimations provided may play a role in agile projects in the industry.