Motivated by data from a large European retail chain, we tackle the newsvendor problem with censored demand observations by a distribution-free model based on a data-driven approach. The model estimates the optimal inventory levels as a linear function of exogenous variables, e.g., price or temperature. To improve the forecast accuracy, we simultaneously estimate unobservable lost sales, determine the coefficients of the exogenous variables which drive demand, and calculate the optimal order quantity. Since demand exceeding supply cannot be recorded, we use the timing of (hourly) sales occurrences to establish (daily) sales patterns. These sales patterns allow conclusions on the amount of unsatisfied demand and thus the true customer demand. To determine the coefficients of the inventory function, we formulate a Linear Programming model that balances inventory holding and penalty costs based on the censored demand observations. In a numerical study with data generated from the normal and the negative binomial distribution, we compare our model with other parametric and non-parametric estimation approaches. We evaluate the performance in terms of inventory and service level for (non-)price-dependent demands and different censoring levels. We find that the data-driven newsvendor model copes especially well with highly censored data and price-dependent demand. In most settings with price-dependent demand, it achieves similar or higher service levels by holding lower inventories than other benchmark approaches from the literature. Finally, we show that the non-parametric approaches are better than the parametric ones based on real data with several exogenous variables where the true demand distribution is unknown.