k nearest neighbor (kNN), which is one of the most typical data mining algorithms, is widely applied in various areas due to its better generation ability and sufficient theory results. The method needs to compute the distances between the test instances and all the training instances during executing prediction. However, it costs substantial time as facing the large-scale data. To solve the problem, we propose an acceleration algorithm for k nearest neighbor classification based on stratified sampling (SS-kNN). In the method, SS-kNN firstly divides the instance space into several subranges with the same number of instances, and then samples instances from each subrange, finally judges which subrange the test instance sit and finds its nearest neighbors from this subrange. Compared with kNN and its variant based on the random sampling, SS-kNN could not only obtain the similar classification accuracy, but also accelerates the running time by an average of 399 and 16 times respectively.