Cet édifice, oeuvre de l’agence d’architectes Hutchison and Wood, est construit entre 1906 et 1908 par la compagnie ferroviaire du Grand Tronc. Cette dernière acquiert les terrains en 1905-1906 et fait démolir les bâtiments qui s’y trouvent. On érige en lieu et place un gratte-ciel de dix étages, le maximum alors autorisé par le règlement en vigueur, entre l’automne 1906 et le printemps 1908. L’édifice possède cependant une structure d’acier suffisamment solide pour ajouter, dans l’éventualité d’une modification à la réglementation municipale, d’autres étages. L’immeuble est relié à l’édifice du Grand Tronc, situé de l'autre côté de la rue, par un tunnel contenant des tuyaux qui alimentent en vapeur son système de chauffage.

Les trois premiers étages de l’édifice sont occupés par la Canadian Express, une filiale du Grand Tronc spécialisée dans les mandats bancaires et les chèques de voyage. On retrouve aux étages supérieurs des services administratifs de la compagnie du Grand Tronc et des bureaux d’entreprises. Dès 1918, la compagnie du Grand Tronc et la Canadian Express deviennent les seuls occupants de l’édifice.

En 1961, le Canadien National, anciennement la compagnie du Grand Tronc, vend l’immeuble au gouvernement du Québec qui y installe les bureaux de nombreux services gouvernementaux, notamment ceux du ministère de l’Immigration et du ministère des Transports. Inoccupé pendant près d’une quinzaine d’années, l’édifice est vendu par le gouvernement québécois en 1996 à une société immobilière et hôtelière espagnole. Celle-ci entreprend en 2000 la rénovation complète de l’immeuble afin de le transformer en établissement hôtelier. L’hôtel Saint-Paul ouvre ses portes en 2001 et se voit attribuer un prix de mise en valeur du patrimoine pour son aménagement intérieur par la Ville de Montréal et ses partenaires.

L’édifice de la Canadian Express est situé rue McGill, un axe urbain en plein boom lors de la construction, en face du siège social du Grand Tronc et à proximité du port. Construit sur une tête d’îlot selon un plan rectangulaire aux deux premiers étages et en U aux étages supérieurs, l’édifice de 10 étages à toit plat présente les principales caractéristiques du gratte-ciel montréalais du début du XXe siècle. Un parement en grès chamois de l’Ohio couvre les trois façades sur rues, tandis que l’arrière est en brique.

L’édifice présente en façade une composition symétrique et doublement tripartite. Verticalement, la partie inférieure à colonnade et à bossages, la partie médiane répétitive et la partie supérieure très élaborée sont typiques du gratte-ciel nord-américain de l’époque. Horizontalement, le traitement crée l’impression d’une colonnade posée sur un socle entre deux massifs de maçonnerie, les « colonnes » de pierre entre les travées de fenêtres laissant deviner la présence de la structure d’acier tout en contribuant à un certain effet de hauteur. À cette composition académique d’esprit beaux-arts s’ajoute un vocabulaire architectural classique, qui possède par surcroît un caractère baroque dû en bonne partie au surdimensionnement des clefs et des claveaux au-dessus des fenêtres, des consoles et des couvrements de certaines baies. Les chapiteaux très ornés des colonnes de la partie inférieure – sans doute de la famille dorique – les festons, les tables décoratives avec gouttes, les masques de lions ajoutent à l’exubérance du décor. Il s’agit en somme d’un gratte-ciel nord-américain tripartite, au décor néo-baroque.

Les hautes baies du rez-de-chaussée, enserrées par une colonnade du côté de la rue McGill, rappellent la présence d’une entreprise de services ayant un lien direct avec le public, la Canadian Express. Sur la rue McGill, trois entrées assurent l’accès à l’édifice. À l’origine, les deux entrées latérales permettent d’accéder respectivement aux services des mandats bancaires et des expéditions du Canadian Express, alors que le portail central donnant accès au centre du lobby actuel menait au hall des ascenseurs. De façon plus générale, la facture architecturale exprime le prestige d’un siège social. Le décor chargé de l’étage du couronnement ainsi que sa hauteur – les plafonds atteignent une hauteur de 13 pieds – semble d’ailleurs évoqué le luxe de locaux réservés à ses dirigeants.