The synthesis of high quality protein crystals is essential for determining their structure. Hence the development of strategies to facilitate the nucleation of protein crystals is of prime importance. Recently, Ghatak and Ghatak [Langmuir 2013, 29, 4373] reported heterogeneous nucleation of protein crystals on nano-wrinkled surfaces. Through a series of experiments on different proteins, they were able to obtain high quality protein crystals even at low protein concentrations and sometimes without the addition of a precipitant. In this study, the mechanism of protein crystal nucleation on nano-wrinkled surfaces is studied through Monte Carlo simulations. The wrinkled surface is modeled by a sinusoidal surface. Free-energy barriers for heterogeneous crystal nucleation on flat and wrinkled surfaces are computed and compared. The study reveals that the enhancement of nucleation is closely related to the two step nucleation process seen during protein crystallization. There is an enhancement of protein concentration near the trough of the sinusoidal surface which aids in nucleation. However, the high curvature at the trough acts as a deterrent to crystal nucleus formation. Hence, significant lowering of the free-energy barrier is seen only if the increase in the protein concentration at the trough is very high.