Sir Charles Barry a réalisé le nouveau palais de Westminster dans un style gothique dit « perpendiculaire », très populaire au XVe siècle et revenu à la mode au XIXe siècle avec le néogothique. Barry lui-même était en réalité un architecte de formation classique, mais fut aidé dans son travail par son collègue Augustus Pugin, rompu aux subtilités du gothique. Westminster Hall, construit au XIe siècle et rescapé des flammes, put être intégré harmonieusement dans la vision d’ensemble de Barry. Pugin fut toutefois mécontent de l’œuvre finale, en particulier à cause de la structure symétrique voulue par Barry. Il le fit savoir dans une remarque restée célèbre : « Du pur grec, monsieur. Des détails Tudor sur un corps classique ».
La pierre utilisée au départ pour la construction, appelée anstone, était une pierre calcaire et magnésienne de couleur sable, extraite au village d’Anston dans le Yorkshire du Sud. La pierre, cependant, commença très vite à se dégrader en raison de la pollution. Bien que ce défaut soit devenu notoire dès 1849, rien ne fut fait pour y remédier pendant le reste du XIXe siècle. Ce n’est qu’au cours des années 1910 que la nécessité de remplacer une partie des pierres s’imposa avec évidence.
En 1928, on eut recours à de la pierre de Clipsham, une pierre calcaire de couleur miel provenant du comté de Rutland. Les travaux furent engagés dans les années 1930 mais durent être interrompus pendant la Seconde Guerre mondiale, pour n’être achevés que dans les années 1950. Dès les années 1960, cependant, des dégâts liés à la pollution réapparurent. Un programme de conservation et de restauration des pierres fut initié pour y remédier en 1981 et se poursuivit jusqu’en 1994.
L’actuel palais de Westminster comprend plusieurs tours. La plus grande et la plus carrée, la tour Victoria (Victoria Tower), se situe à l’angle Sud-Ouest de l’édifice et culmine à 98,5 mètres. Elle fut baptisée ainsi en l’honneur du monarque régnant de l’époque, la reine Victoria. La tour abrite le greffe de la Chambre des Lords (House of Lords' Record Office), qui en dépit de son nom est utilisé par les deux chambres parlementaires. Son sommet arbore le drapeau du palais, qu’il s’agisse du Royal Standard quand le souverain est présent ou plus généralement de l’Union Jack. C’est en effet au pied de la tour Victoria que se situe l’entrée officielle du souverain dans le palais (la Sovereign’s Entrance to the Palace), utilisée notamment à l’occasion des cérémonies d’ouverture du Parlement ou de tout autre événement impliquant la venue du chef de l’État.
La tour Centrale (Central Tower) domine le milieu du palais. Sa hauteur de 91,4 mètres en fait la plus petite des trois principales tours du monument. Contrairement à ses voisines, la tour Centrale est surmontée d’une flèche située immédiatement au-dessus du vestibule central, de forme octogonale.
L’angle nord-ouest supporte la plus célèbre des tours du palais de Westminster, la tour de l’Horloge (Clock Tower) ou tour Saint Étienne (St. Stephen's Tower), haute de 96,3 mètres. Comme son nom l’indique, la tour abrite la grande horloge de Westminster (Great Clock of Westminster), qui possède un cadran sur chacun des quatre côtés. La tour de l’Horloge contient également les cinq cloches du palais, qui sonnent tous les quarts d’heure. La plus grande et la plus célèbre de ces cloches, officiellement appelée la grande cloche de Westminster, est bien davantage connue sous son surnom de Big Ben. Il s’agit de la troisième cloche la plus lourde de tout le Royaume-Uni, avec un poids d’environ 13,8 tonnes. Bien que l’appellation de Big Ben ne s’applique stricto sensu qu’à la cloche, il est courant de désigner par ce terme l’ensemble de la tour de l’Horloge.
Quelques petits jardins entourent le palais de Westminster. Les jardins de la tour Victoria (Victoria Tower Gardens), qui bordent la Tamise au sud du palais, font office de parc public. Le Black Rod's Garden, appelé ainsi en référence à l’huissier de la Chambre des Lords (le Gentleman Usher of the Black Rod), est fermé au public et sert d’entrée privée. La cour du Vieux Palais (Old Palace Yard), face au palais, est pavée et recouverte par sécurité de blocs de béton. D’autres espaces comme le Jardin Cromwell (Cromwell Green) sur le devant, la Cour du Nouveau Palais (New Palace Yard) et le jardin du Speaker (Speaker's Green) au nord sont tous enclos et fermés au public.