Velázquez tomó partido por Catalina y obligó a Cortés a casarse con ella en 1514, comprometiéndose a ser su padrino de bodas y a restablecer su amistad.
Esta relación, así como el conocimiento de las capacidades de Cortés, propiciaron que, después de las dos expediciones a la tierra firme de lo que hoy es México, capitaneadas por Francisco Hernández de Córdoba 1517 y Juan de Grijalva 1518, confiará el gobernador Velázquez a Cortés la organización de una tercera expedición.
El permiso de las expediciones se tramitaban en España y la corona otorgaba el permiso a través de un complicado trámite burocrático a cambio del 20% de lo robado, que con eufemismo llamaban “rescate”. La exploración y fundación requerían otro tipo de trámites que ni Velázquez y mucho menos Cortés tenían en 1519. Velázquez ofreció la expedición en sociedad a otros españoles más ricos de Cuba, pero no la aceptaron por la poca ganancia que ofrecía el gobernador. Cortés se ofreció y aceptó la leonina oferta de Velázquez. Vendió todo cuanto tenía para hacerse cargo de parte de los gastos y buscó socios que pusieran barcos, alimentos, armas y personas, a todos ofreciéndoles grandes ganancias a cambio, las cuales más tarde no cumplió.
Diego Velásquez decidió poner en pie —a su costa, de acuerdo con el procedimiento habitual— una expedición. Pensó en confiar el mando a uno de sus compatriotas de Cuellar, Baltasar Bermúdez, pero éste puso condiciones que disgustaron a Velásquez; el gobernador, airado, lo echó en términos violentos como era su costumbre. Entonces, según Las Casas, Amador de Lares lo
