We report a real-time study on protein crystallization in the presence of multivalent salts using small angle X-ray scattering (SAXS) and optical microscopy, focusing particularly on the nucleation mechanism as well as on the role of the metastable intermediate phase (MIP). Using bovine beta-lactoglobulin as a model system in the presence of the divalent salt CdCl2, we have monitored the early stage of crystallization kinetics which demonstrates a two-step nucleation mechanism: protein aggregates form a MIP, which is followed by the nucleation of crystals within the MIP. Here we focus on characterizing and tuning the structure of the MIP using salt and the related effects on the two-step nucleation kinetics. The results suggest that increasing the salt concentration near the transition zone pseudo-c** enhances the energy barrier for both MIPs and crystal nucleation, leading to slow growth. The structural evolution of the MIP and its effect on subsequent nucleation is discussed based on the growth kinetics. The observed kinetics can be well described, using a rate-equation model based on a clear physical two-step picture. This real-time study not only provides evidence for a two-step nucleation process for protein crystallization, but also elucidates the role and the structural signature of the MIPs in the nonclassical process of protein crystallization.