The kernel trick enables learning of nonlinear decision functions without having to explicitly map the original data to a high dimensional space.However, at test time, it requires evaluating the kernel with each one of the support vectors, which is time consuming. We propose a novel approach for learning nonlinear support vector machine (SVM) corresponding to commonly used kernels in computer vision, namely (i) Histogram Intersection, (ii) χ 2 , (ii) Radial Basis Function (RBF) and (iv) RBF with χ 2 distance, without using the kernel trick. The proposed classifier incorporates non-linearity while maintaining O(D) testing complexity (for D-dimensional space), compared to O(D×Nsv ) (for Nsv number of support vectors) when using the kernel trick. We also promote the idea that such efficient non-linear classifier, combined with simple image encodings, is a promising direction for image classification. We validate the proposed method with experiments on four challenging image classification datasets. It achieves similar performance w.r.t. kernel SVM and recent explicit feature mapping method while being significantly faster and memory efficient. It obtains competitive performance while being an order of magnitudefaster than the state-of-the-art Fisher Vector method and, when combined with it, consistently improves performance with a very small additional computation cost.