Classification based on Nearest Neighbors (NN) is a uniformly good approach to many Pattern Recognition (PR) tasks. However, two important aspects need to be taken into account to actually achieve good performance in practice. The first one is the metric or dissimilarity measure adopted to compare the considered patterns. The second is the computational cost incurred by the NN searching operation. As it is shown in this paper, by using the adequate techniques to cope with these two issues, NN-based classification leads to better results than those obtained by other approaches that have been applied to a task of human banded chromosomes classification.