This work establishes on theoretical basis that Bayesian deep neural network is an effective tool for high-dimensional variable selection with rigorous uncertainty quantification. For a properly configured deep Bayesian neural network (BNN), we show that (1) BNN learns the variable importance effectively in high dimension, and its learning rate can sometimes “break” the curse of dimensionality; (2) BNN’s uncertainty quantification for variable importance is rigorous, in the sense that its 95% credible intervals for variable importance indeed covers the truth 95% of the time (i.e. the Bernstein-von Mises (BvM) phenomenon). The theoretic result suggests a simple variable selection algorithm based on the BNN credible intervals. Extensive simulation confirms the theoretical findings and shows the proposed algorithm outperforms existing classic and machine-learning based variable selection methods especially in high dimension.