Restos arqueológicos hallados en el yacimiento de Las Regueritas sitúan los primeros asentamientos humanos conocidos en la Edad del Bronce. El emplazamiento actual del pueblo se origina en la repoblación medieval llevada a cabo durante el avance de la Reconquista para ocupar las tierras próximas al Duero, reinando Alfonso III en el siglo X. La primera cita documental de Algodre data del año 962, según el Becerro de Sahagún.
Su nombre tiene unas claras connotaciones mozárabes traducidas como “aguas turbias”, en referencia al arroyo que lleva su nombre. El rey Fernando IV cede en 1301, con carácter vitalicio, los lugares de Algodre y Coreses al caballero Juan Alfonso de Benavides en reconocimiento por los servicios prestados; a su muerte, volverán a ser lugares de realengo.
El Convento de las Dueñas, el Cabildo de la Catedral de Zamora y la Encomienda de Valdemimbre eran los mayores propietarios de terreno en Algodre. Las dos primeras instituciones tenían derecho de presentación en el nombramiento del párroco de Santa María de Belén. A mediados del siglo XVIII se contabilizaban 28 vecinos, de los que 17 eran labradores, a los que socorría un Pósito municipal de 200 fanegas de trigo en los momentos de necesidad.