Κατά την αρχαιότητα, η Φοινικούντα, αποτελούσε τμήμα του βασιλείου του Νέστορα στην αρχαία Πύλο, ή την "αμμουδερή Πύλο", όπως αναφέρεται στα ομηρικά έπη.
Υποστηρίζεται από ερευνητές, ότι ιδρύθηκε από τους Φοίνικες που αποίκησαν τα παράλια της Πελοποννήσου στο σημείο αυτό, αν και δεν συμφωνούν όλοι με αυτήν την εκτίμηση.
Στο νεότερο παρελθόν ήταν μικρό ψαροχώρι που ιδρύθηκε, τουλάχιστον από τα μέσα του 19ου αιώνα, και σύμφωνα με την τοπική παράδοση, τη δεκαετία του 1840, από κάτοικους της κοντινής Λαχανάδας, οι οποίοι ήταν πρόσφυγες από την Κρήτη.
Αρχικά ονομάζονταν "Ταβέρνα", λόγω της ταβέρνας, που υπήρχε εκεί. Η ταβέρνα αυτή είναι γνωστή με βάση την τοπική παράδοση ως η «Ταβέρνα του Μπαγάσα» (Παναγόπουλου), ο οποίος θεωρείται ότι ήταν και ο πρώτος κάτοικος του χωριού.
Το 1928 μετονομάστηκε προσωρινά σε "Παραλία Λαχανάδας", ενώ το 1930 έλαβε την σημερινή της ονομασία ως ο "Φοινικούς".
Τις τελευταίες δεκαετίες έχει εξελιχθεί σε ένα από τα σημαντικότερα τουριστικά θέρετρα της Μεσσηνίας, εκμεταλλευόμενη κυρίως το γεγονός πως περιβάλλεται από μεγάλες αμμουδερές παραλίες.
Από τη Φοινικούντα ο επισκέπτης έχει θέα στα δύο από τα τρία μεγαλύτερα νησιά του συμπλέγματος των Μεσσηνιακών Οινουσών: Τη Σχίζα, η οποία έχει ένα αξιόλογο σπήλαιο και την Αγία Μαριανή, στην οποία βρίσκεται το εκκλησάκι της Αγίας Μαρίνας.
