Τη θέση του σημερινού Εθνικού Ιστορικού Μουσείου καταλάμβανε στις αρχές του 19ου αι. η οικία Κοντοσταύλου. Το 1834 το οίκημα αποτέλεσε προσωρινή κατοικία του βασιλιά Όθωνα. Το 1835 προστέθηκε στο κτίριο μια μεγάλη οκταγωνική αίθουσα χωρητικότητας διακοσίων και πλέον ατόμων προκειμένου να χρησιμεύσει ως αίθουσα χορού. Αργότερα, μετά την Επανάσταση της 3ης Σεπτεμβρίου 1843, η αίθουσα αυτή στέγασε τις εργασίες της Εθνικής Συνέλευσης. Αυτό το κτίριο αποτέλεσε το θέατρο της κοινοβουλευτικής ζωής στο μεγαλύτερο μέρος του 19ου αι. και μέχρι το 1935. Εδώ, στις 18 Μαρτίου 1843, έγινε η πρώτη πανηγυρική συνεδρίαση της βουλής κατά την οποία ορκίστηκε ο Όθων υπακοή στο σύνταγμα αναγνωρίζοντας έτσι το πολίτευμα της συνταγματικής μοναρχίας.

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

Τον Αύγουστο του 1858 άρχισαν οι εργασίες της ανέγερσης του κτιρίου. Ωστόσο μόλις την επόμενη χρόνια οι εργασίες σταματούν λόγω ελλείψεως χρημάτων. Όταν, το 1863, ξεκινούν και πάλι οι εργασίες οι κτιριακές ανάγκες έχουν αλλάξει εφόσον δεν υφίσταται πλέον το σώμα της Γερουσίας. Έτσι καλείται ο αρχιτέκτονας Παναγής Κάλκος να μετατρέψει τα σχέδια του Boulanger. Η οικοδόμηση ολοκληρώνεται τελικά το 1871 και στις 11 Αυγούστου 1875 το κτίριο στεγάζει και πάλι της λειτουργίες της Βουλής.