We present NEWMIN, an efficient cube-based algorithm for minimization of single Boolean functions. The salient features of the algorithm are that it does not generate all the prime cubes, and highly efficient heuristics are used to obtain a minimal SPC cover. This leads to savings in computation time and as well as reduces the cost of the solution for some classes of functions. The performance of a prototype implementation of NEWMIN is compared to that of ESPRESSO, the best known logic minimizer currently available. Our algorithm efficiently handles Achilles' heel functions which ESPRESSO finds difficult. Further, as is evident from the results, NEWMIN exhibits better performance on several classes of functions such as parity functions, cyclic functions and most randomly generated functions.