Traffic accidents usually lead to severe human casualties and huge economic losses in real-world scenarios. Timely accurate prediction of traffic accidents has great potential to protect public safety and reduce economic losses. However, it is challenging to predict traffic accidents due to the complex causality of traffic accidents with multiple factors, including spatial correlations, temporal dynamic interactions and external influences in traffic-relevant heterogeneous data. To overcome the above issues, this paper proposes a novel Deep Spatio-Temporal Graph Convolutional Network, namely DSTGCN, to predict traffic accidents. The proposed model is composed of three components: the first component is the spatial learning layer which performs graph convolutional operations on spatial information to learn the correlations in space. The second component is the spatio-temporal learning layer which utilizes graph and standard convolutions to capture the dynamic variations in both spatial and temporal perspective. The third component is the embedding layer which aims to obtain meaningful and semantic representations of external information. To evaluate the proposed model, we collect large-scale real-world data, including accident records, citi-wide vehicle speeds, road networks, meteorological conditions, and Point-of-Interest distributions. Experimental results on real-world datasets demonstrate that DSTGCN outperforms both classical and state-of-the-art methods.