p16INK4a expression is a robust biomarker of senescence for stem cells in human tissues. Here we examined the effect of exercise intensity on in vivo senescence in skeletal muscle, using a randomized counter-balanced crossover design. Biopsied vastus lateralis of 9 sedentary men (age 26.1 ± 2.5 y) were assessed before and after a single bout of moderate steady state exercise (SSE, 60% maximal aerobic power) and high intensity interval exercise (HIIE, 120% maximal aerobic power) on a cycloergometer accumulating same amount of cycling work (in kilojoule). Increases in cell infiltration (+1.2 folds), DNA strand break (+1.3 folds), and γ-H2AX+ myofibers (+1.1 folds) occurred immediately after HIIE and returned to baseline in 24 h (p < 0.05). Muscle p16Ink4a mRNA decreased 24 h after HIIE (−57%, p < 0.05). SSE had no effect on cell infiltration, p16Ink4a mRNA, and DNA strand break in muscle tissues. Senescence-lowering effect of HIIE was particularly prominent in the muscle with high pre-exercise p16INK4a expression, suggesting that exercise intensity determines the level of selection pressure to tissue stem cells at late senescent stage in human skeletal muscle. This evidence provides an explanation for the discrepancy between destructive nature of high intensity exercise and its anti-aging benefits.