The structure entropy is one of the most important parameters to describe the structure property of the complex networks. Most of the existing struc- ture entropies are based on the degree or the betweenness centrality. In order to describe the structure property of the complex networks more reasonably, a new structure entropy of the complex networks based on the Tsallis nonextensive statistical mechanics is proposed in this paper. The influence of the degree and the betweenness centrality on the structure property is combined in the proposed structure entropy. Compared with the existing structure entropy, the proposed structure entropy is more reasonable to describe the structure property of the complex networks in some situations.