Την δεκαετία του 1870 ο έμπορος Βασίλειος Μελάς αγόρασε το οικόπεδο που περικλείεται από τις οδούς Αιόλου, Κρατίνου, Στρέιτ και Σοφοκλέους μπροστά ακριβώς στη πλατεία Κοτζιά ή Δημαρχείου.

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

Μετά το θάνατο του Μελά και της συζύγου του, σύμφωνα με την διαθήκη του, ιδρύθηκε επισήμως το Νηπιακό Επιμελητήριο Μελά (1893) που από τότε διαχειρίζεται το κληροδότημα. Στο μέγαρο στεγάστηκε το Χρηματιστήριο Αθηνών και η Αθηναϊκή Λέσχη, στα τέλη του 19ου αιώνα.

Το 1897 μια πυρκαγιά προκάλεσε σημαντικές καταστροφές στο κτίριο, που αποκαταστάθηκαν δυο χρόνια αργότερα από τον μηχανικό Πέτρο Πρωτοπαπαδάκη. Μεταξύ 1909 και 1932 προστέθηκε τρίτος όροφος βάσει μελέτης του αρχιτέκτονα Οικονόμου και από το 1900 έως το 1973 στο μέγαρο στεγάστηκε το κεντρικό Ταχυδρομείο των Αθηνών.

Αργότερα κρίθηκε διατηρητέο και μισθώθηκε από την Εθνική Τράπεζα, η οποία, σε συνεννόηση με το Νηπιακό Επιμελητήριο Μελά, προχώρησε στην αποκατάσταση του κτιρίου στην αρχική του μορφή, γκρεμίζοντας τον πρόσθετο όροφο, σύμφωνα με μελέτη του αρχιτέκτονα Βλαχόπουλου.