Vanadium dioxide undergoes a first order metal-insulator transition at 340 K. In this Letter, we develop and carry out state-of-the-art linear scaling density-functional theory calculations refined with nonlocal dynamical mean-field theory. We identify a complex mechanism, a Peierls-assisted orbital selection Mott instability, which is responsible for the insulating M-1 phase, and which furthermore survives a moderate degree of disorder.