La mayoría de los historiadores coinciden en que la fundación del municipio está ligada al establecimiento de los frailes Mínimos de San Francisco de Paula en Córdoba, cuando el general de la Orden pidió al Obispo de Córdoba, Don Juan Daza y Osorio, su concurso y el del cabildo, para establecer en esta ciudad un convento de la orden paulina. El propio convento cordobés fue fundado el 18 de febrero de 1510, y el fundador de la Orden de los Mínimos fue beatificado el 7 de julio de 1513, alcanzando la santidad, convirtiéndose en San Francisco de Paula, el 1 de mayo de 1519.

En 1810, cuando España estaba en plena Guerra de la Independencia, La Victoria, en su mayor parte un vasto olivar, era conocida por entonces como La Guijarrosa por formar parte de una vieja y extensa zona de la Rambla con ese mismo nombre. En las inmediaciones del actual pueblo estaba lo que hoy llamamos “La Victoria Vieja”, esto es, la “heredad”, con “casas, bodega, lagar, pila e tinajas, viñas e arboles” y “con todo lo que le pertenece”, que el 21 de noviembre de 1551 compró al curtidor Alonso de Hillón y a su mujer, Isabel Rodríguez, fray Andrés de Santa María para donarla poco después, el 26 de enero de 1552, a los Mínimos o frailes de San Francisco de Paula del Convento de Nuestra Señora de la Victoria de Córdoba.