Implementing spatial structures is common in real-world structures such as bridges, space structures, and ships. This topic has attracted researchers to propose more efficient and pristine methods to obtain more robust and cheaper solutions for spatial structure optimization problems. This paper presents a hybrid approach for simultaneous optimization of sizing and topology of spatial truss structures using genetic programming and local search methods. It aims to find the optimal cross-sectional areas and connectivities between the joints of the truss to achieve minimum structural weight subjected to static constraints. These constraints include structural kinematic stability, maximum allowable stress in elements and maximum nodal displacements in joints. First, this approach utilizes the tree-form representation of trusses and evolves to the optimal structure in search space; afterward, Nelder-Mead algorithm enhances the obtained solution in the final step. The proposed method has the capability of identifying redundant truss members and joints in the design space. Our method applied to some numerical problems and compared with other existing popular and competent techniques in the literature. The findings provided lighter truss structures in comparison with other references.