Label noise can have severe negative effects on the performance of a classifier. Such noise can either arise by adversarial manipulation of the training data or from unskilled annotators frequently encountered in crowd sourcing (e.g. Amazon mechanical turk). Based on the assumption that an expert has provided some fraction of the training data, where labels can be assumed to be true, we propose a new pre-processing method to identify and correct noisy labels via a mutual consistency check using a Parzen window classifier. While the resulting optimization problem turns out to be a combinatorial problem, we design an efficient algorithm for which we provide approximation guarantees. Extensive experimental evaluation shows that our method performs similar and often much better than existing methods for the detection of noisy labels, thus leading to a boost in performance of the resulting classifiers.