Malgré les premiers sondages effectués pour tester la résistance du sol, c'est seulement en commençant les travaux de fondations que la résistance du terrain révèle une mauvaise surprise : une inconsistance du sol du côté de la Seine. Il est alors décidé de bâtir sur pilotis.
3 400 pieux de chêne sont ainsi utilisés, mais au prix d'un retard de huit mois et d'un dépassement de crédits important.
Les fondations terminées, les travaux de maçonnerie peuvent commencer. Ils sont gigantesques : à elle seule, la partie donnant sur l'actuelle avenue Winston-Churchill nécessite 17 000 m2 de pierre, 10 000 m3 de moellons et
2 millions de briques. Pour tenir la course contre la montre, les moyens les plus modernes sont utilisés : grues roulantes, machines à vapeur, pont roulant...
La force humaine est elle aussi requise en masse : au plus fort du chantier,
15 000 ouvriers travaillent – et parfois, se mettent en grève pour obtenir des augmentations de salaire.