A Partial MinSAT instance is a set of clauses where each clause is declared to be either hard or soft, and the Partial MinSAT problem consists in finding an assignment that satisfies all the hard clauses, and minimizes the number of satisfied soft clauses. In this paper we present an algorithm for solving Partial MinSAT that relies on solving a sequence of SAT instances, and report on an empirical investigation that provides evidence that our approach solves crafted and industrial instances that are beyond the reach of existing approaches to Partial MinSAT.