A novel approach based on the direct search method (DSM) is proposed for the solution of combined heat and power (CHP) dispatch problem. To deal with the mutual dependency of multiple-demand and heat–power capacity of cogeneration units, the penalty functions should be considered in DSM to enforce the corresponding violated constraints from the infeasible region into the feasible region. Many nonlinear characteristics of the generator can be handled properly in the direct search procedure. To increase the possibility of exploring the search space where the global optimal solution exists, another effective strategy based on a successive refinement search technique is also proposed to guarantee a possibly complete examination of the solution space. Numerical experiments are included to demonstrate the proposed direct search approach can obtain a higher quality solution than many existing techniques.