On-chip test/diagnosis is proposed to be an effective method to ensure the lifetime reliability of integrated systems. In order to manage the complexity of such an approach, an integrated system is partitioned into multiple modules where each module can be periodically tested, diagnosed and repaired if necessary. The limitation of on-chip memory and computing capability, coupled with the inherent uncertainty in diagnosis, causes the occurrence of misdiagnoses. To address this challenge, a novel incremental-learning algorithm, namely dynamic k-nearest-neighbor (DKNN), is developed to improve the accuracy of on-chip diagnosis. Different from the conventional KNN, DKNN employs online diagnosis data to update the learned classifier so that the classifier can keep evolving as new diagnosis data becomes available. Incorporating online diagnosis data enables tracking of the fault distribution and thus improves diagnostic accuracy. Experiments using various benchmark circuits (e.g., the cache controller from the OpenSPARC T2 processor design) demonstrate that diagnostic accuracy can be more than doubled.