We have investigated the characteristics of gas flow in microchannels under the coupled effects of random surface roughness and velocity slip by the method of computational fluid dynamics. The random surface roughness is modeled by fractal geometry, and the velocity slip on boundary is described by second-order slip law. Results show that the simulated curves obtained by considering both second-order slip law and random surface roughness are in good agreement with experimental data in a range of averaged Knudsen number from 0.025 to 0.59, while the one gained by using Maxwell slip law are in agreement with experimental data in a range of averaged Knudsen number extending up to 0.1. Random surface roughness has an obvious effect on velocity slip: as relative surface roughness increases, velocity slip coefficients decrease. An approximate relation between relative surface roughness and velocity slip coefficients is given according to the results. Last but not least, random surface roughness has a significant effect on the pressure, velocity and Poiseuille number.