Experiments show that the strength of nanostructures can be very high and that strength statistics are dominated by surface flaws. To understand the dependence of strength on the surface morphology, a series of fracture mechanics based Monte-Carlo simulations were performed. The surfaces of previously tested Si nanobeams were measured, statistically characterized and equivalent surfaces were generated. The surface profiles consist of bunched steps with varying heights and widths. At the root of each step, there is a stress singularity defined by a stress intensity factor. The beams were assumed to fail when the stress intensity factor anywhere on the surface exceeds the fracture toughness. In agreement with experiments, simulations show that even a small increase in the surface roughness results in a significant reduction in the strength of nanostructures. Thus, careful attention to the surfaces is essential for optimum strength and reliability at the nanoscale.