Shear yield stress is an important parameter in the processing of colloidal suspensions as it characterizes the solid-to-fluid transition. Although shear rheology of colloidal gel is of widespread academic and industrial interest, first principles theory that connects the microscopic properties to the macroscopic mechanical response in a self-consistent manner is lacking. In this work, we derive a constitutive relation to predict the yield stress for a strongly attractive gel undergoing quasi-static shear deformation as a function of volume fraction, inter-particle potential, contact scale properties and the micro-structure of a strongly-aggregated colloidal gel. The model also predicts the strain at which the colloidal gel network will yield under shear load. To test the model, discrete element simulation is performed using a non-central potential with friction while accounting for the rolling resistance, which is important in real colloidal gel systems. The theoretical predictions are not only in good agreement with the simulation results, but also with previous experiments.