The design of error-correcting codes used in modern communications relies on information theory to quantify the capacity of a noisy channel to send information. This capacity can be expressed using the mutual information between input and output for a single use of the channel; although correlations between subsequent input bits are used to correct errors, they cannot increase the capacity. For quantum channels, it has been an open question whether entangled input states can increase the capacity to send classical information. The additivity conjecture states that entanglement does not help, making practical computations of the capacity possible. Although additivity is widely believed to be true, there is no proof. Here, we show that additivity is false, by constructing a random counter-example. Our results show that the most basic question of classical capacity of a quantum channel remains open, with further work needed to determine in which other situations entanglement can boost capacity.