Perteneció a la baja nobleza castellana, al ser su familia de hidalgos pobres y sin privilegios. Parece probado que sus padres fueron Juan de Montejo y Catalina Álvarez de Tejeda, vecinos de Salamanca, quienes tuvieron, además de a Francisco, otros tres hijos: Juan, que viajaría también al Nuevo Mundo, Mencía y María, esta última madre de Francisco de Montejo, el Sobrino, que acabaría siendo un destacado protagonista de la conquista y colonización de Yucatán. De sus relaciones con Ana de León, miembro de una distinguida familia sevillana, tuvo Francisco de Montejo en 1507 o 1508 un hijo fuera de matrimonio. Legitimado como Francisco de Montejo, el Mozo, sería uno de los principales lugartenientes de su padre y quien realmente culminaría la conquista de Yucatán, al asumir su dirección en la etapa final.

Casi nada se conoce sobre la trayectoria vital de Francisco de Montejo hasta 1513-1514, cuando se unió en Sevilla a Pedrarias Dávila, que había sido nombrado gobernador de Castilla del Oro, la región ístmica del Darién (Panamá). Durante la preparación de su armada a Tierra Firme, Pedrarias lo eligió como oficial y lo envió, por delante de su expedición, a Santo Domingo con la misión de reclutar gente para la colonización del Darién. Sería para entonces, según Bernal Díaz del Castillo, de treinta y cinco años de edad. Más tarde, ya sirviendo en el istmo, Montejo dirigió como capitán, por mandato de Pedrarias, una campaña a la provincia de Zenú, en la región que más tarde sería Nueva Granada. Decepcionado por la política de Pedrarias en el Darién y, sobre todo, por ver que sus servicios no eran debidamente premiados, abandonó la región, junto con otros compañeros de aventura, y se dirigió en 1515 a Cuba para participar en la conquista de la isla que estaba llevando a cabo Diego de Velázquez. Su colaboración en las campañas de pacificación y en la fundación de La Habana fue reconocida por Velázquez con la concesión de encomiendas y de extensos terrenos para el establecimiento de haciendas, destacando entre éstas la estancia de Marién, cerca de La Habana. [...]