Aqueous solutions of proteins and oppositely charged polyelectrolytes were studied at different polyelectrolyte chain length, ionic strength, and protein-protein interaction potential as a function of the polyelectrolyte concentration. One of the protein models used represented lysozyme in aqueous environment. The model systems were solved by Monte Carlo simulations, and their properties were analyzed in terms of radial distribution functions, structure factors, and cluster composition probabilities. In the system with the strongest electrostatic protein-polyelectrolyte interaction the largest clusters were formed near or at equivalent amount of net protein charge and polyelectrolyte charge, whereas in excess of polyelectrolyte a redissolution appeared. Shorter polyelectrolyte chains and increased ionic strength lead to weaker cluster formation. An inclusion of nonelectrostatic protein-protein attraction promoted the protein-polyelectrolyte cluster formation.