Lehečka es hijo de dos atletas. Su padre era nadador y su madre una estrella del atletismo. Ha disfrutado durante mucho tiempo del esquí, el ciclismo y la natación y recuerda haber tocado por primera vez una raqueta de tenis a los tres años. Su abuela, que compitió a nivel nacional, le enseñó el juego a su hermana mayor, por lo que, naturalmente, él quería jugar. Cuando Lehečka era joven, admiraba a Tomáš Berdych y Radek Štěpánek.[2]