国際寝台車会社
最初の列車は1872年10月22日にオーステンデ-ベルリン間で運行を開始した。
1873年1月4日にはワゴン・リ社はマンのマン・ブドワール寝台車会社 (Mann Bourdoir Sleeping Car Company) に買収され、ナゲルマケールスの準備していた列車の多くはマン社の元で運行されることとなった。しかし1875年ごろになるとプルマン社がヨーロッパの寝台列車事業へ本格的に参入しはじめ、マンはヨーロッパからの撤退を決意した。ナゲルマケールスは1876年12月4日にブリュッセルでワゴン・リ社を再建し、マン社の車両を買い取り、その運行していた列車も引き継いだ。新会社にはベルギー国王レオポルド2世も出資しており、この信用がその後の各国政府や鉄道会社との交渉に役立った。
新会社設立時点での所有車両は53両で、ベルギー、ドイツ、オーストリア、フランス、ルクセンブルク、イギリス、ルーマニアの鉄道事業者計19社と契約を結び、16の経路で列車を運行していた。
ワゴン・リ社とプルマン社はその後も激しい競争を繰り広げたが、オリエント急行の成功によりワゴン・リ社の優位が決定的となった。1886年にプルマン社は車両と列車の運行権をワゴン・リ社に売却し、ワゴン・リ社はヨーロッパの寝台列車事業をほぼ独占することに成功した。