The flying car is one of the new vehicles orienting the future aerospace transportation, and its performance is partially determined by gear transmission reliability. In this paper, the test speed changer with offset compound gear (OCG) transmission on a tilting wing flying car was studied for the fatigue reliability estimation and structure optimization. Firstly, the input load spectrum of the OCG speed changer was simulated based on the mission profile. Then the fatigue reliabilities of gear stages and the gear transmission system were estimated based on the stress strength interference theory. During the optimization process, the system fatigue reliability was the objective function, while the number of gear teeth, normal module, face width, pressure angle and shift coefficient were design variables. With the constraints of basic structure, strength and weight, the genetic algorithm was utilized to obtain an optimized solution. The comparison between the optimized structure and the initial one shows that the fatigue reliability of speed changer improves by 3.83% and the mass decreases by 2.4%. This work provides a design method for the development of such systems.