Το 1873 ο Βασίλειος Μελάς αγόρασε τρία οικόπεδα έκτασης περίπου 1.600 τετραγωνικών μέτρων και ανέθεσε στον αρχιτέκτονα Ερνέστο Τσίλλερ τη μελέτη οικοδόμησης διώροφου μεγάρου με υπόγειο. Πρόκειται για το οικοδομικό τετράγωνο που περικλείεται από τις οδούς Αιόλου, Σοφοκλέους, Στρέιτ και Κρατίνου, στη νοτιοανατολική γωνία της τότε πλατείας Λουδοβίκου Α΄, σημερινής πλατείας Δημαρχείου / Κοτζιά.

Ευθύς αμέσως αναθέτει στον αρχιτέκτονα Έρνεστ Τσίλλερ την εκπόνηση σχεδίου για την οικοδόμηση του Μεγάρου. Πρόκειται για ένα από τα πλέον πρώιμα έργα του αρχιτέκτονα, στο οποίο χρησιμοποιεί στοιχεία αντιπροσωπευτικά της δουλειάς του,σύμφωνα με τον αρχιτέκτονα Διονύσιο Βλαχόπουλο, όπως είναι οι πολυεδρικές επιφάνειες των προσόψεων, ο έγχρωμος και γλυπτός διάκοσμος, τα τοξωτά ή και ευθύγραμμα γωνιαία θυρώματα, τα θωράκια, οι επιστέψεις και οι ευθύγραμμες κορνίζες του. Το ‘‘Μέγαρο Μελά’’ ολοκληρώνεται σε πολύ σύντομο χρονικό διάστημα. Επρόκειτο για το μεγαλύτερο ιδιωτικό κτήριο της Αθήνας, η οποία αριθμούσε τότε περί τους 50.000 κατοίκους. Η ανέγερση του κτιρίου κόστισε - όπως είχε λεχθεί - το υπέρογκο, για τότε, ποσόν του ενός εκατομμυρίου δραχμών, όταν ο κρατικός προϋπολογισμός ανερχόταν σε 33 εκατομμύρια δραχμές. Πρώιμο και αντιπροσωπευτικό έργο του Τσίλλερ, το Μέγαρο Μελά συντελεί στο να διατηρείται, μαζί με το Δημαρχείο και την Εθνική Τράπεζα της Ελλάδος, ο αρχικός χαρακτήρας της πλατείας Λουδοβίκου.

Το ισόγειο προς την οδό Αιόλου προοριζόταν για καταστήματα και τη δεκαετία του 1880, τα καταστήματα του ισογείου και τα διαμερίσματα των δύο ορόφων της Μεγάλης Οικίας Μελά ενοικιάζονται σε επαγγελματίες

Στο Μέγαρο στεγάστηκε για ένα μικρό διάστημα (1881) το Χρηματιστήριο Αξιών Αθηνών και αργότερα η Αθηναϊκή Λέσχη (1888-1894). Συγχρόνως αναφέρεται και η χρήση του για εκθέσεις καλλιτεχνών της εποχής. Μετά το θάνατο της Τερψιχόρης Μελά το 1897, το Μέγαρο περιέρχεται στο ίδρυμα που συστάθηκε, το Νηπιακό Επιμελητήριο Μελά. Το 1897 προκαλούνται από πυρκαγιά σοβαρές καταστροφές στο μέγαρο, η επισκευή του οποίου ολοκληρώθηκε το 1899 από τον μηχανικό Πέτρο Πρωτοπαπαδάκη. Υπήρξε επιθυμία του κράτους να τροποποιηθεί το κτίριο ώστε να χρησιμοποιηθεί ως δικαστικό μέγαρο, η οποία και δεν πραγματοποιήθηκε. Το κτήριο μισθώθηκε τελικά στις αρχές του 1900 από το Υπουργείο Συγκοινωνιών, προκειμένου να χρησιμοποιηθεί ως Ταχυδρομικό, Τηλεγραφικό και Τηλεφωνικό Μέγαρο και μάλιστα μέχρι το 1973 στέγαζε το Κεντρικό Ταχυδρομείο. Το 1909 προστίθεται και τρίτος όροφος από τον αρχιτέκτονα Φιλίππο Οικονόμου. Το Μέγαρο Μελά θα ακολουθήσει την ιστορία της δεκαετίας του 1940: όσο διαρκεί ο πόλεμος, θα εγκατασταθούν εκεί η Υπηρεσία Λογοκρισίας, διάφορες στρατιωτικές υπηρεσίες και η Αγγλική Υπηρεσία Διαβιβάσεων, ενώ στην Κατοχή το κτίριο θα επιταχθεί για να εγκατασταθούν γερμανικές υπηρεσίες. Τέλος, κατά τη διάρκεια του Εμφυλίου στο Μέγαρο ήταν στρατωνισμένη αγγλική φρουρά. Το έτος 1977 το μίσθωσε η Εθνική Τράπεζα της Ελλάδος, η οποία το αποκατέστησε στην αρχική του μορφή.