Networks of aggregated colloidal particles are solidlike and can sustain an applied shear stress while exhibiting little or no creep; however, ultimately they will catastrophically fail. We show that the time delay for this yielding decreases in two distinct exponential regimes with applied stress. This behavior is universal and found for a variety of colloidal gel systems. We present a bond-rupture model that quantitatively describes this behavior and highlights the role of mesoscopic structures. Our result gives new insight into the nature of yielding in these soft solid materials.