Pariente próximo del gobernador de Cuba, Diego Velázquez de Cuéllar, y cuñado de Pánfilo de Narváez.

Luchó en Italia y Flandes. Marchó a Cuba, donde tomó parte con Diego Velázquez en la fundación de la ciudad de Trinidad, entre mayo y junio de 1514. Entre febrero de 1519 y junio de 1520 participó con Hernán Cortés en la conquista de México.

El gobernador de Cuba, que era el que había organizado la expedición, había designado a Hernán Cortés para que asumiera el mando, pero cambió de parecer en el último momento, por lo que éste, al que le llegaron rumores de que iba a ser depuesto, decidió salir de la isla a toda prisa y se hizo a la mar el 10 de febrero de 1519, antes de la fecha prevista. En la expedición marchaban tanto hombres de confianza de Cortés como numerosos amigos y parientes del gobernador Velázquez que desconocían las intenciones de su comandante de liberarse de la autoridad del gobernador de Cuba. La armada estaba formada por once navíos, uno de los cuales fue capitaneado por Juan Velázquez de León. Algunos cronistas de la época han sugerido que, cuando se unió a la expedición, tenía alguna cuenta pendiente con la justicia de Cuba, probablemente la muerte de un hombre. [...]