A systematic study into the effect of solid roughness on the slip boundary condition during shear flow is presented. Atomic roughness is modeled by varying the size and spacing between solid atoms at constant packing fraction while the interaction parameters and the thermodynamic state of the fluid are kept constant. It is shown that the fluid structure as manifest in the amplitude of the density oscillations increases with increasing smoothness of the surfaces. The fluid-solid slip length is shown to exhibit nonmonotonic behavior as the solid structure is varied from smooth to rough. Slip occurs for both smooth and rough surfaces, and stick occurs only for surfaces commensurate with the fluid.