Το χωριό Παραδείσια είναι χτισμένο νότια του λεκανοπεδίου της Μεγαλόπολης σε υψόμετρο 520 μέτρων, στον δρόμο Μεγαλόπολης-Καλαμάτας. Αποτελεί δημοτικό διαμέρισμα του Δήμου Μεγαλόπολης και κατά την απογραφή του 2011 απογράφησαν 153 κάτοικοι. Κύριες ασχολίες τους είναι η γεωργία και η κτηνοτροφία.
Στην περιοχή που βρίσκεται το χωριό υπήρχε η αρχαία κώμη Κρώμνος ή Κρώμοι, η οποία σύμφωνα με το μύθο ιδρύθηκε από τον γιο του Λυκάονα, Κρώμο. Η κώμη αυτή θεωρείται μητρόπολη της Κρώμνας του Πόντου. Η θέση της ήταν κοντά στα σύνορα της Αρκαδίας με την Σπάρτη, αλλά και στον δρόμο που ένωνε την Αρκαδία με αυτήν. Το 364 π. Χ. συγκρούστηκαν στην περιοχή οι Αρκάδες με τους Ηλείους και τους Σπαρτιάτες που ήταν τότε σύμμαχοί τους. Αιτία ήταν η προστριβή των Αρκάδων με τους Ηλείους για την κυριότητα της Λασιώνας, μιας μικρής πόλης που βρισκόταν στα όρια της Ηλείας με την Αρκαδία. Οι Σπαρτιάτες υπό τον βασιλιά τους Αρχίδαμο κατέλαβαν το ύψωμα πάνω από τους Κρώμνους που δέσποζε της οδού Μεγαλόπολης – Μεσσήνης. Όταν όμως αποχώρησε η κύρια δύναμη των Σπαρτιατών, αφήνοντας μια μικρή φρουρά πάνω στο λόφο, οι Αρκάδες αντεπιτέθηκαν και κύκλωσαν τους Σπαρτιάτες. Στη συνέχεια ο Αρχίδαμος επανήλθε, αλλά οδηγήθηκε σε νέα ήττα. Μια νέα σύγκρουση έγινε το 352 π.Χ., μεταξύ των Μεγαλοπολιτών και των Σπαρτιατών που μάλιστα αποτέλεσε αφορμή για να εκφωνήσει ο Αθηναίος ρήτορας Δημοσθένης τον υπέρ Μεγαλοπολιτών λόγο του.
Λίγο μετά την απελευθέρωση του 1821 οι αρχές του τόπου ήταν οι Δημογεροντίες. Όταν καταργήθηκαν το 1835 δημιουργήθηκαν Δήμοι, με τα Παραδείσια να αποτελούν τον «Δήμο Γαθεών». Η ονομασία του δήμου οφειλόταν στην αρχαία πόλη «Γαθεαί» που βρισκόταν λίγο έξω από το χωριό και την οποία αναφέρει ο Παυσανίας στα «Αρκαδικά». Το 1840 ο Δήμος Γαθεών ενσωματώθηκε στον Δήμο Λυκοσούρας, μέχρι το 1914 που έγινε κοινότητα. Μέχρι το 1929 το χωριό ονομαζόταν Κούρταγας (Κούρτ-Αγάς=Λύκος-Αγάς).
Έξω από το χωριό βρίσκεται το κεφαλόβρυσο του Αγίου Κοσμά. Κοντά στα Παραδείσια είναι ο οικισμός Φαναίτη που αποτελεί τμήμα τους.