Photoionization using attosecond pulses can lead to the formation of coherent superpositions of the electronic states of the parent ion. However, ultrafast electron ejection triggers not only electronic but also nuclear dynamics—leading to electronic decoherence, which is typically neglected on time scales up to tens of femtoseconds. We propose a full quantum-dynamical treatment of nuclear motion in an adiabatic framework, where nuclear wave packets move on adiabatic potential energy surfaces expanded up to second order at the Franck-Condon point. We show that electronic decoherence is caused by the interplay of a large number of nuclear degrees of freedom and by the relative topology of the potential energy surfaces. Application to H2O, paraxylene, and phenylalanine shows that an initially coherent state evolves to an electronically mixed state within just a few femtoseconds. In these examples the fast vibrations involving hydrogen atoms do not affect electronic coherence at short times. Conversely, vibrational modes involving the whole molecular skeleton, which are slow in the ground electronic state, quickly destroy it upon photoionization.