New calculations for vanadium dioxide, one of the most controversially discussed materials for decades, reveal that band theory as based on density functional theory is well capable of correctly describing the electronic and magnetic properties of the metallic as well as both the insulating M1 and M2 phases. Considerable progress in the understanding of the physics of VO2 is achieved by the use of the recently developed hybrid functionals, which include part of the electron-electron interaction exactly and thereby improve on the weaknesses of semilocal exchange functionals as provided by the local density and generalized gradient approximations. Much better agreement with photoemission data as compared to previous calculations is found and a consistent description of the rutile-type early transition-metal dioxides is achieved.