Developments in sensor techniques enable the continuous monitoring of the health of an operating system. The resulting condition data provides an opportunity for better prediction of failures and thereby for improving maintenance decisions. In this study, we consider condition-based maintenance for a single unit with an unknown, non-decreasing deterioration process and unknown failure behavior. Building on, but different from the existing maintenance optimization literature, we present the first fully data-driven approach, where the condition threshold triggering maintenance is based purely on past condition data and failures. Numerical results for a gamma deterioration process show that the maintenance threshold resulting from our data-driven approach converges to the optimal threshold. The threshold is set higher during the initial runs-to-failure, and this helps to explore the deterioration process. An encouraging result is that the convergence is especially fast during the first few runs-to-failure so that the expected cost rate quickly converges to the minimum cost rate.