For networks of pulse-coupled oscillators with complex connectivity, we demonstrate that in the presence of coupling heterogeneity precisely timed periodic firing patterns replace the state of global synchrony that exists in homogenous networks only. With increasing disorder, these firing patterns persist until a critical temporal extent is reached that is of the order of the interaction delay. For stronger disorder the periodic firing patterns cease to exist and only asynchronous, aperiodic states are observed. We derive self-consistency equations to predict the precise temporal structure of a pattern from a network of given connectivity and heterogeneity. Moreover, we show how to design heterogeneous coupling architectures to create an arbitrary prescribed pattern.