En 2013, Martín Lestido devient champion de Galice sur route dans la catégorie espoirs (moins de 23 ans). Il brille également dans les courses par étapes chez les amateurs. Il rejoint ensuite l'équipe continentale roumaine Tusnad[3]. Bon grimpeur, il se distingue sur le Tour de Bulgarie en terminant neuvième du classement général en 2015 puis deuxième d'une étape sur l'édition 2016.
En 2017, il redescend chez les amateurs au club Super Froiz en Galice. Pour son retour en Espagne, il remporte le Tour de La Corogne[4] ainsi que le Tour de Galice[5]. Il continue à courir dans cette équipe galicienne jusqu'en 2019.