It is well accepted that combined heat and power (CHP) generation can increase the efficiency of power and heat generation at the same time. With the increasing penetration of CHPs, determination of economic dispatch of power and heat becomes more complex and challenging. The CHP economic dispatch (CHPED) problem is a challenging optimization problem due to non-linearity and non-convexity in both objective function and constraints. Hence, in this paper a novel meta-heuristic algorithm, namely improved artificial bee colony (IABC) algorithm is proposed to solve the CHPED problem. The valve-point effects, power losses as well as the feasible operation region of CHP units are taken into account in the proposed CHPED problem model and the optimal dispatch of power/heat outputs of CHP units is determined via the proposed IABC algorithm. The proposed algorithm is applied on three test systems, in which two of them are large-scale CHPED benchmarks. The obtained results and comprehensive comparison with available methods, demonstrate the superiority of the proposed algorithm for dealing with non-convex and constrained CHPED problem.