A design optimization of a staggered pin fin heat sink made of a thermally conductive polymer is presented. The influence of several design parameters like the pin fin height, the diameter, or the number of pins on thermal efficiency of the natural convection heat sink is studied. A limited number of representative heat sink designs were selected by application of the design of experiments (DOE) methodology and their thermal efficiency was evaluated by application of the antecedently validated and verified numerical model. The obtained results were utilized for the development of a response surface and a typical polynomial model was replaced with a neural network approximation. The particle swarm optimization (PSO) algorithm was applied for the neural network training providing very accurate characterization of the heat sink type under consideration. The quasi-complete search of defined solution domain was then performed and the different heat sink designs were compared by means of thermal performance metrics, i.e., array, space claim and mass based heat transfer coefficients. The computational fluid dynamics (CFD) calculations were repeated for the most effective heat sink designs.