Depletion interactions induced by the addition of soluble, non-adsorbing polymer significantly influence the phase behavior of protein solutions. Here we investigate the influence of polymer on the strength of interactions, phase behavior and nucleation kinetics of protein solutions. The strength of protein interactions induced by the presence of polymer is characterized through protein solution second virial coefficient measurements, Working with lysozyme and poly (ethylene glycol) (PEG), we find that the second virial coefficient, B-2 is a non-monotonic function of polymer concentration at modest ionic strengths (where the protein molecules behave essentially as hard spheres). At high ionic strengths, B-2 and solubility are independent of polymer concentration. The effect of polymer on protein solution phase behavior is studied by carrying out equilibrium or solubility measurements (fluid-crystal boundary) and cloud point measurements (liquid-liquid boundary). A scintillation cell setup is used to determine nucleation induction times with and without the presence of polymer. We present a detailed experimental investigation of the influence of PEG on protein pair interactions, phase behavior and nucleation kinetics.