We investigate yielding in a colloidal gel that forms a heterogeneous structure, consisting of a two-phase bicontinuous network of colloid-rich domains of fractal clusters and colloid-poor domains. Combining large amplitude oscillatory shear measurements with simultaneous small and ultra-small angle neutron scattering (rheo-SANS/USANS), we characterize both the nonlinear mechanical processes and strain amplitude-dependent microstructure underlying yielding. We observe a broad, three-stage yielding process that evolves over an order of magnitude in strain amplitude between the onset of nonlinearity and flow. Analyzing the intracycle response as a sequence of physical processes reveals a transition from elastic straining to elastoplastic thinning (which dominates in region I) and eventually yielding (which evolves through region II) and flow (which saturates in region III), and allows quantification of instantaneous nonlinear parameters associated with yielding. These measures exhibit significant strain rate amplitude dependence above a characteristic frequency, which we argue is governed by poroelastic effects. Correlating these results with time-averaged rheo-USANS measurements reveals that the material passes through a cascade of structural breakdown from large to progressively smaller length scales. In region I, compression of the fractal domains leads to the formation of large voids. In regions II and III, cluster-cluster correlations become increasingly homogeneous, suggesting breakage and eventually depercolation of intercluster bonds at the yield point. All significant structural changes occur on the micron-scale, suggesting that large-scale rearrangements of hundreds or thousands of particles, rather than the homogeneous rearrangement of particle-particle bonds, dominate the initial yielding of heterogeneous colloidal gels. (C) 2014 The Society of Rheology.