パレオエクスプレスは21世紀を走る唯一のC58形蒸気機関車

C58 形は、1938年（昭和13年）から1947年にかけて427両が製造された鉄道省（国鉄の前身）の機関車である。全国に配備された客貨万能の機関車で、安定した性能を有することから、お召し列車を何度か牽引している。

パレオエクスプレスは、土曜日と日曜日、熊谷駅と三峰口駅の間を1往復する。所要時間は約2時間半。
機関車の先頭には、季節に合わせたヘッドマークを付けている。この日は 桜 のヘッドマークが掲げられていた。

パレオエクスプレスを牽引するC58 363は、太平洋戦争のさなか、1944年（昭和19年）に製造された。

1973年（昭和48年）に現役を引退し、埼玉県吹上町立吹上小学校の校庭で静態保存されていた。しかし、1988年（昭和63年）のさいたま博覧会（3月19日から5月29日まで熊谷市で開催）にともない復活した。

2004年（平成16年）には還暦を迎え、21世紀を走る唯一のC58形となっている。

牽引される12系客車は、2012年（平成24年）に運行25周年を記念してダークグリーンから赤茶色にあらためられた。

2019年（令和元年）5月1日、新元号を祝って「SLおめでとう令和号」を運行した。

パレオエクスプレスは、国内最年長の機関士、田村力 （つとむ） さん（70）によって運行されてきた。1966年（昭和41年）に23歳で国鉄の機関士となり、一時は電車の運転士となったが、1990年（平成2年）に秩父鉄道に出向しパレオエクスプレスの機関士を務めた。

田村さんは「SLは奥が深い」という。弁の開き具合を細かく調節し、蒸気の消費を最小限にとどめて石炭を節約する。急発進などで乗客に不快な衝撃を与えないよう、乗客数の違いに応じて加減を変える。すべて経験に基づく感覚が頼りだ。「乗客が多いか少ないかは、始発駅で動き出す時の“感じ”で分かる」という。

田村さんは2013年（平成25年）11月に引退した。秩父鉄道には教え子の機関士が5人いる。
「秩父鉄道も生え抜きだけで運行できる態勢になり、うれしい。SLの運転は誇りであり、楽しかった」と振り返った。引退後は5人の孫娘と一緒に客として乗り、教え子たちの上達ぶりを見るのが楽しみだという。