This paper introduces Minimal Norm Support Vector Machines (MNSVM) as the new fast classification algorithm originating from minimal enclosing ball approach and based on combining state of the art minimal norm problem solvers and probabilistic techniques. Our approach significantly improves the time performance of the SVM's training phase. Moreover, the comparison with other SVM classification techniques based on Sequential Minimal Optimization algorithm, over several large real data sets within the strict validation frame of a double (nested) cross-validation, reveals huge similarity in the classification accuracy. The results shown are promoting MNSVM as outstanding alternative for handling large and ultra-large datasets in a reasonable time without switching to various parallelization schemes for SVMs algorithms proposed recently.