We develop two approaches for analyzing the approximation error bound for the Nyström method that approximates a positive semidefinite (PSD) matrix by sampling a small set of columns, one based on a concentration inequality for integral operators, and one based on random matrix theory. We show that the approximation error, measured in the spectral norm, can be improved from $O(N/\sqrt {m})$ to $O(N/m^{1 - \rho })$ in the case of large eigengap, where $N$ is the total number of data points, $m$ is the number of sampled data points, and $\rho \in (0, 1/2)$ is a positive constant that characterizes the eigengap. When the eigenvalues of the kernel matrix follow a $p$-power law, our analysis based on random matrix theory further improves the bound to $O(N/m^{p - 1})$ under an incoherence assumption. We present a kernel classification approach based on the Nyström method and derive its generalization performance using the improved bound. We show that when the eigenvalues of the kernel matrix follow a $p$-power law, we can reduce the number of support vectors to $N^{2p/(p^{2} - 1)}$, which is sublinear in $N$ when $p > 1+\sqrt {2}$, without seriously sacrificing its generalization performance.