Attempts for higher output power and thermal efficiency of gas turbines make the inlet temperature of turbine to be far beyond the material melting temperature. Therefore, to protect the airfoil in gas turbine from hot gas and eventually prolong the lifetime of the blade, internal and film cooling structures with better thermal performance and cooling effectiveness are urgently needed. However, the traditional way of proceeding involves numerous simulations, additional experiments, and separate trials. Optimization of turbine cooling structures is an effective way to achieve better structures with higher overall performances while considering the multiple objectives, disciplines or subsystems. In this context, this paper reviews optimization research works on film cooling structures and internal cooling structures in gas turbines by means of various optimization methods. This review covers the following aspects: (A) optimization of film cooling conducted on flat plates and on turbine blades or vanes; (B) optimization of jet impingement cooling structures; (C) optimization of rib shapes, dimple shapes, pin–fin arrays in the cooling channels; (D) optimization of U-bend shaped cooling channels, and internal cooling systems of turbine blades or vanes. The review shows that through a reliable and accurate optimization procedure combined with conjugate heat transfer analysis, higher overall thermal performance can be acquired for single-objective or multi-objectives balanced by other constrained conditions. Future ways forward are pointed out in this review.