Nació en Sevilla durante el reinado de Carlos III. Sus padres eran Cayetano Valdés Bazán, comisario de Guerra de los Reales Ejércitos, y María Antonia de Flórez Peón. Era, asimismo, sobrino del bailío Antonio Valdés Bazán, capitán general de la Armada, a la que gobernó con indudable acierto. Cayetano Valdés sentó plaza de guardia marina en Cádiz el 23 de abril de 1781 con apenas catorce años y ya pertenecía a la Orden de San Juan, pero su precocidad no fue obstáculo para que, terminados sus estudios, embarcara en la escuadra de Luis de Córdova que sostenía el bloqueo de Gibraltar, encontrándose también en el combate sostenido por dicha Escuadra contra la flota inglesa del almirante Howe en 1782.

En un rotundo cambio de escenario, participó en la expedición de Argel a las órdenes de Antonio Barceló, formándose en acciones de guerra que determinarían su carácter. La nota más destacada de su hoja de servicios en tiempos de juventud, fue su participación en la expedición de Malaspina, de quien gozó extrema confianza hasta el punto de proponerlo, junto a su compañero Dionisio Alcalá Galiano, para la exploración del estrecho de Fúcar, misión que cumplieron de forma satisfactoria. [...]