Catalytic colloidal swimmers that propel due to self-generated fluid flows exhibit strong affinity for surfaces. Here, we report experimental measurements of a significant dependence of such microswimmers' speed on the nearby substrate material. We find that speeds scale with the solution contact angle θ on the substrate, which relates to the associated hydrodynamic substrate slip length, as V∝(cosθ+1)^{-3/2}. We show that such dependence can be attributed to osmotic coupling between swimmers and substrate. Our work points out that hydrodynamic slip at nearby walls, though often unconsidered, can significantly impact microswimmer self-propulsion.