Paredes de Nava is a municipality located in the province of Palencia, Castile and León, Spain.

It is the birthplace of Renaissance painter Pedro Berruguete. Some paintings by him can be seen in the predella of the local church of Santa Eulalia. Other sights include the church of St. Martin (15th century, renovated in the 18th century).