The gear tooth fillet is an area of maximum bending stress concentration. However, its profile is typically less specified in the gear drawing and hardly controlled during gear inspection in comparison with the gear tooth flanks. This paper presents a fillet profile optimization technique for gears with symmetric and asymmetric teeth based on FEA and a random search method. It allows achieving substantial bending stress reduction in comparison with traditionally designed gears. This bending stress reduction can be traded for higher load capacity, longer lifetime, lower noise and vibration and cost reduction.