The effect of polymer conjugation on the interactions between proteins in solution is evaluated by systematic analysis of the second virial coefficient (A2) for the particular example of single- and double-PEGylated bovine serum albumin (PEG-BSA) in dilute PBS solution. The effect of PEGylation on A2 is found to sensitively depend on both the composition and the distribution of PEG segments within the conjugate. Most importantly, at a given PEG volume fraction, A2 significantly increases with the degree of polymerization of tethered chains. Hence, a lesser number of long chains is more effective in solubilizing BSA than a correspondingly larger number of short chains. Analysis of the hydrodynamic radii of protein-PEG conjugates suggests that the increased solubility is concurrent with a structural transition in the case of high molecular PEG grafts that results in compact core-shell-type structures. The results reveal a link between the composition, structure, and solubility of polymer conjugates that might benefit the understanding of their biochemical characteristics and their design for functional material applications.