北海商船
小樽利礼航路は、1901年に小樽の藤山海運が運航を開始、道庁命令航路として運航していたが、1936年には稚内-利礼航路の開設で役割が減少し1953年に北海商船が航路を継承して運航を開始。設立当初は新潟商船倉庫(後の三井近海汽船)や三井船舶が主な株主となり、東京都中央区の三井ビルに本社と小樽市に小樽事務所を置いた。東京都には1968年頃まで本社を置き、1969年には小樽市に本社を移転している。
1976年12月22日、新おたる丸が礼文島金田ノ岬付近で吹雪により座礁、現場の地形と冬期の海況から短期間での離礁が困難と判断されたため、稚内利礼運輸から第三利礼丸を用船して運航した。その後、新おたる丸は放棄されたため、1977年に室戸汽船から第五室戸丸を購入して就航させた。