The complexation between one polyelectrolyte and one protein has been examined by employing a simple model system solved by Monte Carlo simulations. The polyelectrolyte was composed of a sequence of negatively charged hard spheres, and the protein was represented by a hard sphere with embedded pH-dependent discrete charges, the positions of which were taken from lysozyme. A short-range attractive interaction between the polyelectrolyte and the protein accounting for hydrophobic interactions completed the model. The complexation was found to depend decisively on the charge status of the protein model as well as on the presence of the short-range attractive interaction. In particular, the complexation weakens at decreasing ionic strength except for the highest positive protein net charge considered, and in the absence of the short-range attraction, a positively charged protein was required to obtain a complex. The distribution of the polyelectrolyte beads was inhomogeneous at the protein surface, and the polyelectrolyte contracted upon complexation. Finally, the protein model with discrete charges gave a stronger complex than the corresponding protein model with a homogeneous surface charge density.