With the growth of intelligent transportation, reliable urban traffic prediction has become increasingly important in people’s lives. It does, however, confront the following challenges: First, the structure of traffic networks is usually constructed by researchers using domain knowledge , which is thus frequently uncertain. Second, the spatio-temporal dependence is complex, which is embodied in that the influence weights of various nearby roads section are uncertain and the status of roads section changes over time. Thus, even though the network structure is fully known, the spatio-temporal dependencies between roads’ sections are uncertain. However, to the best of our knowledge, few existing works have been able to address all challenges, and the performance of existing methods can be further improved. In this paper, the motivation is to address the uncertainty of traffic network in terms of connectivity and the dependency among nodes. Thus, we propose a Bayesian Spatio-Temporal Graph Attention Neural Networks (BST-GAT), which uses Bayesian theorem and a random block model of mixed membership to reconstruct the network during the neighborhood aggregation process to address the uncertainty of the network structure. In addition, BSTGAT uses the attention mechanism and RNN to address the uncertainty of the spatio-temporal dependence. Extensive experiments on two benchmark datasets demonstrate that BSTGAT is capable of effectively solving the uncertainty of the network structure and spatio-temporal dependencies, and it significantly outper-forms state-of-the-art model due to its higher effect and robustness.