We introduce performance-based regularization (PBR), a new approach to addressing estimation risk in data-driven optimization, to mean-CVaR portfolio optimization. We assume the available log-return data is iid, and detail the approach for two cases: nonparametric and parametric (the log-return distribution belongs in the elliptical family). The nonparametric PBR method penalizes portfolios with large variability in mean and CVaR estimations. The parametric PBR method solves the empirical Markowitz problem instead of the empirical mean-CVaR problem, as the solutions of the Markowitz and mean-CVaR problems are equivalent when the log-return distribution is elliptical. We derive the asymptotic behavior of the nonparametric PBR solution, which leads to insight into the effect of penalization, and justification of the parametric PBR method. We also show via simulations that the PBR methods produce efficient frontiers that are, on average, closer to the population efficient frontier than the empirical approach to the mean-CVaR problem, with less variability.