Partial multi-label learning (PML) deals with the problem where each training example is associated with an overcomplete set of candidate labels, among which only some candidate labels are valid. The task of PML naturally arises in learning scenarios with inaccurate supervision, and the goal is to induce a multi-label predictor which can assign a set of proper labels for unseen instance. The PML training procedure is prone to be misled by false positive labels concealed in the candidate label set, which serves as the major modeling difficulty for partial multi-label learning. In this paper, a novel two-stage PML approach is proposed which works by eliciting credible labels from the candidate label set for model induction. In this first stage, the labeling confidence of candidate label for each PML training example is estimated via iterative label propagation. In the second stage, by utilizing credible labels with high labeling confidence, multi-label predictor is induced via pairwise label ranking coupled with virtual label splitting or maximum a posteriori (MAP) reasoning. Experimental studies show that the proposed approach can achieve highly competitive generalization performance by excluding most false positive labels from the training procedure via credible label elicitation.