Problem definition: We study the practice-motivated problem of dynamically procuring a new, short-life-cycle product under demand uncertainty. The firm does not know the demand for the new product but has data on similar products sold in the past, including demand histories and covariate information such as product characteristics. Academic/practical relevance: The dynamic procurement problem has long attracted academic and practitioner interest, and we solve it in an innovative data-driven way with proven theoretical guarantees. This work is also the first to leverage the power of covariate data in solving this problem. Methodology: We propose a new combined forecasting and optimization algorithm called the residual tree method and analyze its performance via epiconvergence theory and computations. Our method generalizes the classical scenario tree method by using covariates to link historical data on similar products to construct demand forecasts for the new product. Results: We prove, under fairly mild conditions, that the residual tree method is asymptotically optimal as the size of the data set grows. We also numerically validate the method for problem instances derived using data from the global fashion retailer Zara. We find that ignoring covariate information leads to systematic bias in the optimal solution, translating to a 6%–15% increase in the total cost for the problem instances under study. We also find that solutions based on trees using just two to three branches per node, which is common in the existing literature, are inadequate, resulting in 30%–66% higher total costs compared with our best solution. Managerial implications: The residual tree is a new and generalizable approach that uses past data on similar products to manage new product inventories. We also quantify the value of covariate information and of granular demand modeling.