Securing matings is a key determinant of fitness and in many species males are the sex that engages in mate searching. Searching for mates is often associated with increased mobility. This elevated investment in movement is predicted to trade-off with sperm competitiveness, but few studies have directly tested whether this trade-off occurs. Here, we assessed whether artificial selection on mobility affected sperm competitiveness and mating behavior, and if increased mobility was due to increased leg length in red flour beetles (Tribolium castaneum). We found that in general, males selected for decreased mobility copulated for longer, stimulated females more during mating and tended to be better sperm competitors. Surprisingly, they also had longer legs. However, how well males performed in sperm competition depended on females. Males with reduced mobility always copulated for longer than males with high mobility, but this only translated into greater fertilization success in females from control populations and not the selection populations (treatment females). These results are consistent with a mate-searching/mating-duration trade-off and broadly support a trade-off between mobility and sperm competiveness.