Η ανοικοδόμηση του παλατιού ξεκίνησε γύρω στο 500 π. Χ. και καταστράφηκε από πυρκαγιά στις αρχές του 4ου αι. π. Χ. χωρίς να ξανακτιστεί. Μετά από εξέταση της αρχιτεκτονικής και της κεραμικής του χώρου, οι ανασκαφείς διαπίστωσαν ότι στο παλάτι διακρίνονται τέσσερις οικοδομικές φάσεις. Κατά τη δεύτερη περίοδο ανοικοδόμησης το παλάτι επεκτάθηκε με την προσθήκη νέων δωματίων αλλά ο αρχιτεκτονικός χαρακτήρας παρέμεινε ο ίδιος με την πρώτη φάση του κτιρίου. Κατά την τρίτη οικοδομική φάση το παλάτι πήρε την οριστική του μορφή η οποία διαφέρει από αυτήν της πρώτης φάσης. Κατά την τέταρτη φάση έγιναν κάποιες μικρές αλλαγές και προσθήκες στο χώρο χωρίς όμως να αλλοιώνουν το σχέδιο της τρίτης φάσης.

Η πρώτη φάση του Παλατιού χαρακτηρίζεται έντονα από Ανατολικά αρχιτεκτονικά στοιχεία με την τριμερή οργάνωση των επίσημων διαμερισμάτων. Αυτό ίσως να οφείλεται στα ιστορικά γεγονότα της εποχής αφού το 499 π. Χ., το βασίλειο των Σόλων συμμετείχε στην εξέγερση των κυπριακών βασιλείων εναντίον των Περσών κατακτητών. Μετά από πολιορκία πέντε μηνών οι Πέρσες κατέστειλαν την εξέγερση και είναι τότε που πιθανόν το βασίλειο του Μαρίου (στην περιοχή της σημερινής Πόλης της Χρυσοχούς, επαρχία Πάφου) έκτισε το παλάτι των Σόλων με σκοπό να ελέγχει τη γύρω περιοχή. Το 449 π. Χ. ο Αθηναίος στρατηγός Κίμωνας κατέλαβε το γειτονικό βασίλειο του Μαρίου, καθαίρεσε τον φίλο-περσικό άρχοντα και τοποθέτησε φιλέλληνα βασιλιά. Κατά την ίδια περίοδο πιθανόν να μετακίνησε και τον άρχοντα στο παλάτι του Βουνίου αφού βλέπουμε ότι τα Ανατολικά στοιχεία στην αρχιτεκτονική του παλατιού αντικαταστάθηκαν με αρχιτεκτονικά στοιχεία προερχόμενα από τον Ελληνικό χώρο. Έτσι, η τριμερής διαρρύθμιση των επίσημων δωματίων άλλαξε και ο κεντρικός χώρος του παλατιού πήρε τη μορφή μεγάρου με Μυκηναϊκά χαρακτηριστικά.

Τόσο το παλάτι όσο και τα άλλα μικρότερα κτίσματα γύρω του (ως επί τω πλείστον ιερά) περιβάλλονταν από τείχος δίνοντας έτσι την εντύπωση οχυρού. Η αρχική είσοδος του παλατιού βρισκόταν στα νοτιοδυτικά. Σε μεταγενέστερο στάδιο όμως η είσοδος αυτή σφραγίστηκε και μετακινήθηκε στα βορειοανατολικά με μια εντυπωσιακή κλίμακα που οδηγούσε σε ορθογώνια εσωτερική αυλή μπροστά από τα επίσημα διαμερίσματα. Τρεις στοές περιέβαλλαν την εσωτερική αυτή αυλή στις τρεις της πλευρές. Τα μεγαλύτερο μέρος της αυλής το κατέβαλλε μια δεξαμενή. Τα ιδιωτικά διαμερίσματα βρίσκονταν γύρω από την αυλή και στη νοτιοανατολική γωνία των διαμερισμάτων υπήρχαν τρία δωμάτια που λειτουργούσαν ως λουτρά.

Στο ανατολικό τμήμα του παλατιού βρισκόταν μια μεγάλη ανοικτή αυλή με δύο σειρές από αποθηκευτικά δωμάτια τα οποία ήταν διώροφα. Προς το μέρος της θάλασσας υπήρχε δεξαμενή με μεγάλο στόμιο η οποία σήμερα διατηρείται σε καλή κατάσταση. Οι δεξαμενές ήταν ουσιαστικά στοιχεία στη θέση αυτή αφού το Βουνί δε διέθετε φυσικές πηγές νερού. Στα νοτιοδυτικά η αυλή επικοινωνούσε με την κουζίνα και τους χώρους υπηρεσίας. Στην αυλή των δωματίων της κουζίνας, κάτω από μια ξύλινη κλίμακα που οδηγούσε στο δεύτερο όροφο του παλατιού, βρέθηκε ο γνωστός θησαυρός του Βουνίου: χρυσά και αργυρά κοσμήματα και νομίσματα. Στα δάπεδα των αποθηκευτικών χώρων διατηρούνται σήμερα τα κωνικά βαθουλώματα τα οποία συγκρατούσαν αποθηκευτικά αγγεία.

Κατά μήκος της βόρειας πλευράς και της νότιας γωνιάς του παλατιού βρίσκεται αριθμός ιερών. Τα ιερά αυτά ήταν απλά ορθογώνια κτίσματα με ανοικτές αυλές και διαφόρων ειδών βωμούς. Το σημαντικότερο ιερό βρισκόταν στο ψηλότερο σημείο του λόφου, στα νότια του παλατιού και έχει ταυτιστεί με ιερό της Αθηνάς. Το ιερό αυτό είχε τη μορφή μεγάλης ορθογώνιας αυλής με αγάλματα. Οι θήκες των αγαλμάτων διατηρούνται μέχρι σήμερα. Στα δεξιά της εισόδου της αυλής βρισκόταν ένας μεγάλος ημικυκλικός βωμός. Το κυρίως ιερό βρισκόταν πίσω από την αυλή, στα δυτικά και περιλάμβανε ένα μικρό ορθογώνιο δωμάτιο στο εσωτερικό του οποίου βρέθηκαν τα διάσημα χάλκινα αγάλματα. Στα νοτιοανατολικά του ιερού υπήρχαν τρία παρακείμενα δωμάτια τα οποία λειτουργούσαν ως θησαυροφυλάκια σχεδιασμένα με πρότυπα αυτά των Δελφών. Στα δωμάτια αυτά φυλάσσονταν τα αναθήματα προς τη θεά.