Η Αναγέννηση ιδρύθηκε το 19851981.<ref>{{Cite web|url=http://www.sigmalive.com/news/local/377161/astego-to-prosfygiko-somateio-anagennisi-elpida-mouttalou|title=Αστεγο το προσφυγικό Σωματείο Αναγέννηση – Ελπίδα Μουττάλου|last=|first=|date=2016-11-05|website=www.sigmalive.com|publisher=|archiveurl=https://web.archive.org/web/20161216212902/http://www.sigmalive.com/news/local/377161/astego-to-prosfygiko-somateio-anagennisi-elpida-mouttalou|archivedate=2016-12-16|accessdate=2016-12-16}}</ref> Αρχικά αγωνιζόταν στις διοργανώσεις της [[Ποδοσφαιρική Ομοσπονδία Αγροτικών Σωματείων Πάφου|Ποδοσφαιρικής Ομοσπονδίας Αγροτικών Σωματείων Πάφου]] (ΠΟΑΣΠ). Το 1986 η Αναγέννηση Μούτταλου εντάχθηκε στη [[Δ΄ κατηγορία ποδοσφαίρου ανδρών Κύπρου|Δ΄ κατηγορία]] και στις τάξεις της [[Κυπριακή Ομοσπονδία Ποδοσφαίρου|Κυπριακής Ομοσπονδίας Ποδοσφαίρου]] (ΚΟΠ) μέσω του [[Πρωτάθλημα ένταξης|πρωταθλήματος ένταξης]]. Στην πρώτη συμμετοχή της στο πρωτάθλημα, την [[Δ΄ κατηγορία ποδοσφαίρου ανδρών Κύπρου 1986-87|περίοδο 1986-87]], τερμάτισε στην ένατη θέση του ομίλου της.<ref name=":0" /> Την [[Δ΄ κατηγορία ποδοσφαίρου ανδρών Κύπρου 1987-88|επόμενη περίοδο]] τερμάτισε στη 13η θέση και υποβιβάστηκε στα αγροτικά (τοπικά) πρωταθλήματα.<ref name=":1" /> Συνέχισε στις διοργανώσεις της (ΠΟΑΣΠ).
Το 1995 ενοποιήθηκε με την [[Ελπίδα Προσφύγων Πάφου]] δημιουργώντας την ομάδα «Αθλητική Ένωση Αναγέννηση Ελπίδα Προσφύγων Πάφου».<center>
