We present a new algorithm for addressing nonconvex Mixed-Integer Nonlinear Programs (MINLPs) where the cost function is of nonlinear least squares form. We exploit this structure by leveraging a Gauss-Newton quadratic approximation of the original MINLP, leading to the formulation of a Mixed-Integer Quadratic Program (MIQP), which can be solved efficiently. The integer solution of the MIQP is used to fix the integer variables of the original MINLP, resulting in a standard Nonlinear Program. We introduce an iterative procedure to repeat the optimization of the two programs in order to improve the solution. To guide the iterations towards unexplored regions, we devise a strategy to partition the integer solution space based on Voronoi diagrams. Finally, we first illustrate the algorithm on a simple example of MINLP and then test it on an example of real-world complexity concerning the optimal control of an energy system. Here, the new algorithm outperforms state-of-the-art methods, finding a solution with a lower objective value, at the cost of requiring an increased runtime compared to other approximate methods.