Using a laser polarization gradient, we realize 3D Sisyphus cooling of $^{171}$Yb$^+$ ions confined in and near the Lamb-Dicke regime in a linear Paul trap. The cooling rate and final mean motional energy of a single ion are characterized as a function of laser intensity and compared to semiclassical and quantum simulations. Sisyphus cooling is also applied to a linear string of four ions to obtain a mean energy of 1-3 quanta for all vibrational modes, an approximately order-of-magnitude reduction below Doppler cooled energies. This is used to enable subsequent, efficient sideband laser cooling.