The problem of band-gap structure were studied for the spatial beam phononic crystal to solve the stability of complex structure such as space truss, framae and so on. The axial, torsional, flexural and coupled vibration equations of beam element were solved by the traveling method. The dispersion equation and band-gap properties were forward obtained by the traveling wave method combined with the continuous conditions of force and displacement at the node of beam phononic crystal and Bloch theory. Genetic algorithm was used to reverse obtained the spatial beam phononic crystal structure with specified location and width of band gap by optimizing the material and structure size, taking relative bandwidth (the ratio total width and lowest angular frequency of band gap). The optimal solution was obtained by combing with engineering experience and economic benefit. This paper provided a new way for the study of band gap structure of spatial beam phononic crystal.