Class-conditional noise commonly exists in machine learning tasks, where the class label is corrupted with a probability depending on its ground-truth. Many research efforts have been made to improve the model robustness against the class-conditional noise. However, they typically focus on the single label case by assuming that only one label is corrupted. In real applications, an instance is usually associated with multiple labels, which could be corrupted simultaneously with their respective conditional probabilities. In this paper, we formalize this problem as a general framework of learning with Class-Conditional Multi-label Noise (CCMN for short). We establish two unbiased estimators with error bounds for solving the CCMN problems, and further prove that they are consistent with commonly used multi-label loss functions. Finally, a new method for partial multi-label learning is implemented with the unbiased estimator under the CCMN framework. Empirical studies on multiple datasets and various evaluation metrics validate the effectiveness of the proposed method.