Las primeras noticias escritas que aparecen sobre Malcocinado se encuentro en el Archivo Histórico de Azuaga, bien sea en libros de Acuerdos, o en documentos (más en estos últimos), su aparición data desde el siglo XVI, y sus temas abarcan, desde lo que hoy tenemos por impuestos (alcabalas, diezmos, etc, hasta las penas impuestas por corte de leña y algún que otro pleito entre vecinos.) Se hace mención durante los siglos XVI, XVII y XVII, a la villa de Malcocinado y a sus bodegas de vino.

Cuando al hacerse la división provincial, se «iniciaron los trámites para pedir la separación de Guadalcanal, la solicitud se hizo con el nombre de ALDEANUEVA DE LA VICTORIA.

Su caserío es abierto y de traza notablemente regular, compuesto por edificaciones blancas de modelo campesino que originan un conjunto alegre, pulcro y bien cuidado, con abundancia de gratas zonas ajardinadas.

IGLESIA PARROQUIAL DE SAN ANTONIO DE PADUA

Edificación de nave única dividida en cuatro tramos mediante arcos de ladrillo visto, que se cubren con bóvedas con aristas.

La construcción actual data de 1931, cuando se completó el proyecto del nuevo templo sobre el terreno en el que existió el anterior (cuya construcción puede remontarse al siglo XVIII), y que se demolió en los años 20 debido a su estado ruinoso.

Los primeros datos de la parroquia se encuentran en el archivo de la ‘Iglesia Parroquial de Santa María la Mayor’ de Guadalcanal, ya que hasta 1842 en que se independizó, el pueblo perteneció a dicho municipio como aldea.