Dès 1946 les ingénieurs savaient que la traversée de la Garonne par les chemins de fer se ferait du côté de Paludate. Le nom de l'ouvrage était déjà écrit sur un plan 14 ans avant sa construction : elle s'appellera "Passerelle" (rien à voir, donc - contrairement à ce qui été beaucoup écrit - avec le passage piéton qui lui sera accolé). Le terme désigne les ouvrages d'art en métal, légers "comme un arc-en-ciel" ("Ode à Bordeaux," par Lodoïste Lataste, compositeur béglais).

Mais malgré cette prévision d'emplacement, la Gare d'Orléans sera placée face au centre ville, pour des raisons de prestige. Donc en cul-de-sac, ce qui causera immédiatement son déclin !

La Passerelle fut conçue par l'ingénieur Stanislas de La Roche-Tolay, assisté de Paul Régnault, tous deux ingénieurs de la Compagnie du Midi. On sait depuis peu que des parois en croisillons sont plus efficaces que des parois pleines, car elles sont quasiment aussi résistantes pour un poids très inférieur. Elles permettent des piles plus minces, opposant moins de résistance au courant (3 à 6 m. cube / seconde). Le choix est vite fait.

Le chantier est confié à la Cie Générale de Matériel de Chemins de Fer. Le directeur général, François Pauwel, est en Belgique. Le directeur de la section française, Charles Nepveu (orthographié "Neveu" par Eiffel), est à Paris. Il envoie à Bordeaux son meilleur ingénieur, de seulement 26 ans, Gustave Eiffel. Sur le chantier, c'est lui le patron.

Il décide de standardiser les pièces, ce qui réduit les frais et accélère la construction. Au lieu de recourir au rivetage à la main, il fait installer une riveteuse sur le quai rive droite. La prépartion du chantier lui est pénible : le 29 juin 1858 il écrit : "le travail est si vaste et les visiteurs si nombreux que la journée de 5h00 du matin à 9h00 du soir s'écoule à une vitesse incroyable, et que le sommeil et la fatigue me prennent aussitôt après le dîner".

La construction commence le 15 août 1858 par un pont en bois servant d'échafaudage. Les piles sont faites d'anneaux creux assemblés bout à bout. Pour les enfoncer, à 25 m. de profondeur, Eiffel améliore une technique récente consistant à creuser par l'intérieur, sous air comprimé pour chasser la boue au dehors tandis qu'à l'intérieur les ouvriers creusent à pied sec, ou presque. Il module l'appui vertical grâce à des presses à vapeur à 200 t. de pression. Le matériel n'étant pas arrivé à temps, la première pile a nécessité 53 jours de creusement. La technique d'Eiffel étant appliquée, la même opération prit seulement une dizaine de jours ! Ensuite la pile était remplie de béton.

Un jour un ouvrier tombe à l'eau. Quelqu'un se jette dans la Garonne pour le sauver. C'est Eiffel ! Les ouvriers ne l'oublieront pas...

L'ingénieur Régnault fera, dans son traité sur la construction des ponts métalliques, les éloges de la technique utilisée par Eiffel, mais sans jamais mentionner son nom. Pourtant, d'après Eiffel lui-même, Régnault lui témoigna toujours une grande amitié.

Enfin le chantier s'achève. Le 7 juillet 1860 Eiffel écrit : "Le pont s'avance bien (...) il y a cependant à la suite un malheureux petit viaduc qui pourrait bien me retenir encore une quinzaine". Il faisait référence au Viaduc de Paludate, faisant la jonction entre la Passerelle et la plateforme de la Gare St-Jean.

L'esthétique de la Passerelle est influencée par la mode médiévale succédant à Viollet-Leduc : le sommet des piles est ceinturé de bandes lombardes (pas si rares dans le bâti ferroviaire à cette époque).

Le 8 juillet les ouvriers offrent à Eiffel une médaille sur laquelle on peut lire "Hommage - Souvenir - Gratitude" !

Le 13 août 1860 à 19h00 un train de machines à vapeur avance prudemment sur le viaduc pour en éprouver la résistance. Il s'y arrête, et tout le monde prend la pose pour être photographié par Alphonse Terpereau, photographe officiel de la Compagnie du Midi.

La Passerelle est décorée en suivant la mode médiévale inspirée par Viollet-Leduc. Les piles sont coiffées d'une ceinture de bandes lombardes, et pour l'inauguration on a construit un décor fait de grandes tour carrées avec créneaux et machicoulis ! La structure est en bois.

L'ouverture à l'exploitation se fit le 1er septembre pour les marchandises, et le 5 novembre pour les voyageurs. Suite à quoi Eiffel construisitt aussi le Pont du Guit, au sud du bâtiment de la gare.

Rapidement Eiffel se détacha de Nepveu avec beaucoup de désinvolture - ce dernier en conçut beaucoup d'amertume - et quitta Pauwels le 31 mars 1860 pour l'aventure de Suez, qui ne tourna pas à son avantage...

En 1862 - année où Eiffel se maria - il construisit un passage piéton ajouté en accolement côté aval, suite à la demande de nombreux bordelais. C'est sans doute à cette époque qu'on ajouta, à chaque extrémité du pont, un linteau en métal, très décoré, portant les armes de Madrid côté sud et celles de Paris côté nord.  Ce dernier se retrouva bientôt seul à orner le pont, et disparaîtra à son tour à une date indéterminée, mais probablement avant 1900.

De 1875 à 1991 la Passerelle fit l'objet de 15 travaux (ou tranches de travaux) d'entretien. Entre 1923 et 1959 fut procédé, en trois fois, au remplacement du platelage en bois par de la tôle en acier, et autres renforcements. Cette amélioration entraîna une rigidification du pont, ce qui accéléra le fissurage en étoile autour de nombreux rivets. Mais il n'y avait guère d'alternative : un train en 1860 pesait environ 200 tonnes, un siècle plus tard il pesait quatre fois plus lourd. 

En 1981 le passage pour piétons, dont le plancher n'était que très vaguement entretenu, fut démoli malgré les protestations de nombreux bordelais, obligés désormais de faire un long détour par le Pont de Pierre.

Aujourd'hui l'avenir de la Passerelle est peu clair. Elle est protégée et ne sera donc pas détruite. Elle est proposée depuis plusieurs années à Bordeaux Métropole pour le prix de 1,00 € symbolique, mais la question de l'accès côté rive gauche pose des défis complexes, donc coûteux, aussi la transaction n'est-elle toujours pas lancée.

De nombreux projets restent dans les tiroirs, mais est-on certains d'être si novateurs ? Pas sûr, car :
- une pétition pour faire de la passerelle un pont mixte rail-route a été lancée en... 1886 !
- le franchissement de la Garonne par 4 voies ferrées, comme aujourd'hui, a été proposé par la Cie du Midi en... 1914 !

Concluons avec un propos de Bertrand Lemoine, Ingénieur-Architecte, directeur de recherche au CNRS : "Le pont [ferroviaire] de Bordeaux est sans doute le plus ancien pont à treillis encore subsistant".