Deep insight can be gained into the nature of nonclassical correlations by studying the quantum operations that create them. Motivated by this we propose a measure of nonclassicality of a quantum operation utilizing the relative entropy to quantify its commutativity with the completely dephasing operation. We show that our measure of nonclassicality is a sum of two independent contributions, the generating power--its ability to produce nonclassical states out of classical ones, and the distinguishing power--its usefulness to a classical observer for distinguishing between classical and nonclassical states. Each of these effects can be exploited individually in quantum protocols. We further show that our measure leads to an interpretation of quantum discord as the difference in superdense coding capacities between a quantum state and the best classical state when both are produced at a source that makes a classical error during transmission.