With the rapid development of the Internet of Things (IoT), modern Maritime Transportation Systems (MTS) have played a crucial role in the transport industry. The various potential privacy and security concerns (such as vessels’ location tracking, message tampering, unauthorized access to data, etc.) have increased substantially in IoT-enabled MTS. Considering the above issues, we propose a secure, robust, and efficient authentication scheme for MTS based on Elliptic-Curve Cryptography (ECC) and Hash-based Message Authentication Code (HMAC) called PSAS-MTS. The proposed PSAS-MTS scheme not only monitors the vessel’s condition but also ensures protection against collisions in route management and provides safety to the vessel’s passengers. The scheme uses simple XOR, a cryptographic one-way hash, an ECC cryptosystem, and HMAC to achieve a high level of security in MTS. The formal security analysis is carried out using a well-known Real-Or-Random (ROR) model, which ensures the security harness features. A rigorous informal security analysis is also done, which ensures various privacy and security features such as mutual authentication, anonymity, forward and backward secrecy, etc. The proposed PSAS-MTS scheme resists various possible well-known active and passive security attacks. The performance analysis shows that the proposed PSAS-MTS scheme is more efficient in terms of computation and communication overheads when compared to other competitive schemes.