We prove an $epsilon$-regularity theorem for vector-valued p-harmonic maps, which are critical with respect to a partially free boundary condition, namely that they map the boundary into a round sphere. This does not seem to follow from the reflection method that Scheven used for harmonic maps with free boundary (i.e., the case $p=2$): the reflected equation can be interpreted as a $p$-harmonic map equation into a manifold, but the regularity theory for such equations is only known for round targets. Instead, we follow the spirit of the last-named authors recent work on free boundary harmonic maps and choose a good frame directly at the free boundary. This leads to growth estimates, which, in the critical regime $p=n$, imply Holder regularity of solutions. In the supercritical regime, $p < n$, we combine the growth estimate with the geometric reflection argument: the reflected equation is super-critical, but, under the assumption of growth estimates, solutions are regular. In the case $p<n$, for stationary $p$-harmonic maps with free boundary, as a consequence of a monotonicity formula we obtain partial regularity up to the boundary away from a set of $(n-p)$-dimensional Hausdorff measure.