Selon le National Register of Historic Places, le nouveau bâtiment, appelé Bâtiment d'État, de la Guerre et de la Marine (State, War, and Navy Building) car il abritait les trois départements (équivalent de ministères) d'État, de la Marine et de la Guerre fut construit entre 1871 et 1888. La construction, supervisée par l'architecte Alfred B. Mullett, fut réalisée dans un style Second Empire français. Immeuble de 5 étages en granit, il offrait alors plus de 553 pièces et bureaux, 2 800 mètres de couloirs, pour une superficie totale de 61 550 m2
La plus grande partie de l'intérieur a été conçue par Richard von Ezdorf, utilisant une structure en fonte anti-incendie et des éléments décoratifs dont des verrières massives au-dessus de chaque escalier et des poignées de porte avec des moulures en fonte indiquant lequel des trois départements (État, Marine ou Guerre) occupait la pièce. Les occupants d'origine de l'éfifice ont rapidement été à l'étroit et durent occuper d'autres bâtiments et finalement, à la fin des années 1930, l'abandonnèrent totalement. L'immeuble apparu progressivement peu pratique et fut menacé de démolition en 1957. En 1981, des travaux débutèrent pour restaurer toutes les suites ministérielles. Le bureau principal du secrétaire à la Marine fut restauré en 1987 et est maintenant utilisé comme bureau de cérémonie pour le vice-président des États-Unis. Plusieurs études ont été menées afin de moderniser l'immeuble, mais elles ne furent jamais mises en œuvre. Peu de temps après les attentats du 11 septembre 2001, la partie donnant sur la 17e Rue fut vidée et la modernisation de ses espaces laissés libres débuta (certaines anciennes cachettes abritant des documents datant des années 1910 à 1940 furent ainsi mises à jour). L'immeuble continue d'abriter différentes agences qui composent le Bureau exécutif du président, comme le Bureau du vice-président, le Bureau de la gestion et du budget (OMB) et le Conseil national de sécurité. Cependant, son principal but publique est de servir comme bureau de cérémonie du vice-président.
Plusieurs personnalités nationales ont participé à des évènements historiques entre les murs de granit du Old Executive Office Building. Theodore Roosevelt, Franklin D. Roosevelt, William Howard Taft, Dwight D. Eisenhower, Lyndon B. Johnson, Gerald Ford et George H. W. Bush ont tous eu un bureau dans cet immeuble avant de devenir président. Il a abrité 16 secrétaires à la Marine, 21 secrétaires à la Guerre et 24 secrétaires d'État. Winston Churchill a arpenté ses couloirs et les émissaires japonais y rencontrèrent le secrétaire d'État Cordell Hull quelques heures après l'attaque de Pearl Harbor. Le Président Herbert Hoover occupa le bureau du secrétaire à la Marine pendant quelques mois suite à un incendie dans le Bureau ovale le jour de Noël 1929. Dwight D. Eisenhower y tint la première conférence de presse télévisée d'un président américain dans la salle du Traité indien en janvier 1955. Richard Nixon y avait un bureau privé durant sa présidence.
Un petit incendie le 19 décembre 2007 endommagea les bureaux de l'équipe du vice-président dont le bureau servant à l'accueil des personnalités.
Le Old Executive Office Building est devenu un National Historic Landmark. Mais son style ne plut pas toujours à tous, ainsi Mark Twain y faisait référence comme « le plus laid bâtiment d'Amérique » et Harry Truman l'appelait « la plus grande monstruosité en Amérique ».
Le 9 novembre 1999, il fut renommé bâtiment du bureau exécutif Eisenhower (Eisenhower Executive Office Building) en l'honneur de l'ancien président Dwight D. Eisenhower.