Pairwise learning usually refers to the learning problem that works with pairs of training samples, such as ranking, similarity and metric learning, and AUC maximization. To overcome the challenge of pairwise learning in the large scale computation, this paper introduces Nystrom sampling approach to the coefficient-based regularized pairwise algorithm in the context of kernel networks. Our theorems establish that the obtained Nystrom estimator achieves the minimax error over all estimators using the whole data provided that the subsampling level is not too small. We derive the function relation between the subsampling level and regularization parameter that guarantees computation cost reduction and asymptotic behaviors’ optimality simultaneously. The Nystrom coefficient-based pairwise learning method does not require the kernel to be symmetric or positive semi-definite, which provides more flexibility and adaptivity in the learning process. We apply the method to the bipartite ranking problem, which improves the state-of-the-art theoretical results in previous works.