This paper presents an optimal shape design methodology for mixed convection problems. The Navier-Stokes equations and the Continuous Sensitivity Equations (CSE) are solved using an adaptive finite-element method to obtain flow and sensitivity fields. A new procedure is presented to extract accurate values of the flow derivatives at the boundary, appearing in the CSE boundary conditions for shape parameters. Flow and sensitivity information are then employed to calculate the value and gradient of a design objective function. A BFGS optimization algorithm is used to find optimal shape parameter values. The proposed approach is first verified on a problem with a closed form solution, obtained by the method of manufactured solutions. The method is then applied to determine the optimal shape of a model cooling system.