The viscosity of blood has long been used as an indicator in the understanding and treatment of disease, and the advent of modern viscometers allows its measurement with ever-improving clinical convenience. However, these advances have not been matched by theoretical developments that can yield a quantitative understanding of blood's microrheology and its possible connection to relevant biomolecules (e.g., fibrinogen). Using coarse-grained molecular dynamics and two different red blood cell models, we accurately predict the dependence of blood viscosity on shear rate and hematocrit. We explicitly represent cell-cell interactions and identify the types and sizes of reversible rouleaux structures that yield a tremendous increase of blood viscosity at low shear rates. We also present the first quantitative estimates of the magnitude of adhesive forces between red cells. In addition, our simulations support the hypothesis, previously deduced from experiments, of yield stress as an indicator of cell aggregation. This non-Newtonian behavior is analyzed and related to the suspension's microstructure, deformation, and dynamics of single red blood cells. The most complex cell dynamics occurs in the intermediate shear rate regime, where individual cells experience severe deformation and transient folded conformations. The generality of these cell models together with single-cell measurements points to the future prediction of blood-viscosity anomalies and the corresponding microstructures associated with various diseases (e.g., malaria, AIDS, and diabetes mellitus). The models can easily be adapted to tune the properties of a much wider class of complex fluids including capsule and vesicle suspensions.