You are forgetting about the aqueous environment the protein is folding in. Typically proteins fold in such a way that hydrophobic sections of the protein are hidden from the aqueous environment and hydrophilic sections are not. This means that even though the entropy decreases in just the confirmation of the protein, the entropy of the aqueous environment increases much more. The environment has many more accessible orientations when the hydrophobic sections are hidden and the hydrophilic sections are exposed, and thus entropy overall still increases.
A recent SciShow video covers this exact idea in the context of protein folding as well as other biological scenarios.
A somewhat more quantitative picture is given here
In biology, entropy is very often the driving force, for instance for the burial of hydrophobic protein domains. Imagine a water molecule in a tetrahedron. The tetrahedron has four corners, and the water has two hydrogens, so you can place the molecule in $4\text{ choose }2 = 6$ orientations. If you add a nonpolar group of a neighboring molecule at one corner of the tetrahedron, only three of the six states remain favorable (by still allowing hydrogen bonding). So $\Delta S_\text{hydrophobic} = k_b\ln(3) - k_b\ln(6) < 0$, meaning that entropy has decreased.
An incorrect and simplistic view of protein folding is as follows. An unfolded protein has high configurational entropy but also high enthalpy because it has few stabilizing interactions. A folded protein has far less entropy, but also far less enthalpy. There is a trade-off between $H$ and $S$ here. Note that because $\Delta G = \Delta H - T\Delta S$, increased temperature weights the $S$ term more heavily, meaning that higher temperature favors unfolding.
That entire explanation only considers the energy of the protein and not that of the solvent. In fact, hydrophobic domains of a protein constrain the possible configurations of surrounding water (see explanation above), and so their burial upon folding increases the water’s entropy. Moreover, it turns out that the hydrogen bonding of polar residues and the backbone is satisfied both in an unfolded state (by water) and in a folded state (by each other). Therefore enthalpy is “zero sum,” and protein folding is driven almost entirely by entropy.
A much more detailed description can be found here, although I will say I have only skimmed this; I have not read through it carefully.