In this paper, we consider the problem of optimal partial hedging for a contingent claim subject to a preset hedging budget constraint. Under some technical assumptions on the hedged loss function and the market pricing functional, the optimal partial hedging strategy, which minimizes the conditional value-at-risk (CVaR) of the hedger's total risk exposure, is derived explicitly. Some in-depth analysis is conducted for a utility-based indifference pricing functional. Ample numerical examples are presented to highlight the comparative advantages of the proposed CVaR-based hedging strategy relative to other hedging strategies including expected shortfall hedging, VaR-based hedging strategies and the CVaR hedging strategy of Melnikov and Smirnov. Among these hedging strategies, the numerical examples demonstrate that our proposed CVaR-based hedging is more robust and more effective in terms of managing the tail risk of the hedger's risk exposure.