This paper proposes a new learning system of low computational cost, called fast polynomial kernel learning (FPL), based on regularized least squares with polynomial kernel and subsampling. The almost optimal learning rate as well as the feasibility verifications including the subsampling mechanism and solvability of FPL are provided in the framework of learning theory. Our theoretical assertions are verified by numerous toy simulations and real data applications. The studies in this paper show that FPL can reduce the computational burden of kernel methods without sacrificing its generalization ability very much.