In ocean transportation, detecting vessel delays in advance or in real time is important for fourth-party logistics (4PL) in order to fulfill the expectations of customers and to help customers reduce delay costs. However, the early detection of vessel delays faces the challenges of numerous uncertainties, including weather conditions, port congestion, booking issues, and route selection. Recently, 4PLs have adopted advanced tracking technologies such as satellite-based automatic identification systems (S-AISs) that produce a vast amount of real-time vessel tracking information, thus providing new opportunities to enhance the early detection of vessel delays. This paper proposes a data-driven method for the early detection of vessel delays: in our new framework of refined case-based reasoning (CBR), real-time S-AIS vessel tracking data are utilized in combination with historical shipping data. The proposed method also provides a process of analyzing the causes of delays by matching the tracking patterns of real-time shipments with those of historical shipping data. Real data examples from a logistics company demonstrate the effectiveness of the proposed method.