Belçikalı genç bir girişimci olan Georges Lambert Nagelmackers Amerika Birleşik Devletleri’nde bindiği, rahatsız ve yolcuların mahremiyetini sağlamayan Pullman trenlerine alternatif olarak uzun mesafede konfor, zerafet ve rafine bir hizmet sunmayı düşünerek Wagon-Lits yataklı vagonları tasarladı. Daha sonra adı Uluslararası Yataklı Vagon ve Büyük Avrupa Ekspresleri Şirketi (Compagnie Internationale des Wagons-Lits et Des Grands Express Européens) olarak değiştirecek ilk şirketini kurdu (1873). Yataklı vagonlar Paris-Ostende, Paris-Köln ve Paris-Viyana hatlarında hizmet vermeye başladı.

George’un babası, iş adamı Edmond Nagelmakers ve Belçika Kralı II. Léopold projenin destekçileriydi. George Nagelmakers, Yataklı Vagon şirketinden sonra bir vagon üretim şirketi ve Uluslararası Büyük Oteller Şirketini kurdu ve trenin geçtiği 10 ülkede 20 otel açtı. Bu zincir aynı zamanda dünyadaki ilk otel zinciriydi.

05.06.1883 tarihinde ilk Paris-İstanbul Seferi duyuruldu ve 04.10.1883 tarihinde ilk Orient-Express yolculuğu başladı. Yolcular, Paris’ten yola çıkıp Strazburg, Münih, Viyana, Budapeşte ve Bükreş’e, Tuna üzerinde bir feribotla Bulgaristan’da Rusçuk’a, oradan başka bir trenle Varna’ya geçip, Karadeniz’de 14 saatlik bir yolculukla İstanbul’a ulaştı. Yetmiş altı saatlik yolculuk 08.10.1883 tarihinde İstanbul’da tamamlandı. Tren 20.10.1883 tarihinde Paris’e döndü. Bu deneme seferinde 24 yolcunun tamamı erkekti ve silahlıydı. Her ihtimale karşı yanlarında bir tabanca bulundurmaları söylendi.

Haftada iki seferle başlayan tren, 1885 yılından sonra Viyana’ya kadar günlük olarak yola çıkıyordu. Hattın direkt İstanbul’a kadar ulaşması II. Abdülhamit’in izniyle ve rayların döşenmesi sonucu ancak 1. 06. 1889 yılında gerçekleşti. 3.094 kilometrelik yolculuk süresi 77 saat 46 dakikaya düştü. Böylece İstanbul lüks ve romantizmin sembolü olan trenin son durağı haline geldi. 1913 yılında Balkan Savaşları dolayısıyla yolculuklar Belgrad’da sonlanıyordu. Birinci Dünya Savaşı sırasında yataklı vagonlara el kondu ve sonra yok edildi. Sadece 2419 Numaralı vagon, Mareşal Foch için büro haline getirildi ve 11.11.1918 tarihindeki ateşkes antlaşması bu vagonda imzalandı.

1919 yılında tekrar seferlere başlayan tren, Simplon tünelinden geçerek Londra’dan, Milano ve Venedik üzerinden geçerek İstanbul’a kadar ulaşımı sağladı. Orient Express, Simplon Orient Express ve Alberg Orient-Express olarak üç farklı yoldan giden trenlerin simgesi olan koyu lacivert vagonlar bu dönemde hizmete sunuldu. 1930’lı yıllarda cam ustası René Lalique ve dekoratör René Prou’nun dekorasyonlarıyla trenin sunduğu lüks ve kalite daha da belirginleşti. 1883 yılından 1950’li yıllara kadar aralarında Agatha Christie, Leon Tolstoy, Pierre Loti, Albert Einstein, Joséphine Baker, Arabistanlı Lawrence, Marlène Dietrich, Gabrielle Chanel, Jean Cocteau, Ingrid Bergman ve Mata Hari’nin de olduğu pek çok ünlü Orient Express’le İstanbul’a geldi. Agatha Christie’nin yazdığı Şark Ekpresi’nde Cinayet romanı (1934) trene olan ilgiyi arttırdı.

İkinci Dünya Savaşı sırasında seferler yine durdu, 1945 yılında tekrar başladı. 1977 yılına kadar yolculuklarına devam eden Orient Express, talebin azalması dolayısıyla hizmetlerini sona erdirdi. 2011 yılında Fransız Ulusal Demiryolları Şirketi – SNCF tarafından satın alınan şirket lüks ve nostaljik bir yolculuk yapmak isteyen üst gelir grubu turistlere hizmet vermek üzere tekrar hizmet vermeye başladı.