Port address hopping (PAH) communication is a powerful network moving target defense (MTD) mechanism. It was inspired by frequency hopping in wireless communications. One of the critical and difficult issues with PAH is synchronization. Existing schemes usually provide hops for each session lasting only a few seconds/minutes, making them easily influenced by network events such as transmission delays, traffic jams, packet dropouts, reordering, and retransmission. To address these problems, in this paper we propose a novel selfsynchronization scheme, called ‘keyed-hashing based self-synchronization (KHSS)’. The proposed method generates the message authentication code (MAC) based on the hash based MAC (HMAC), which is then further used as the synchronization information for port address encoding and decoding. Providing the PAH communication system with one-packet-one-hopping and invisible message authentication abilities enables both clients and servers to constantly change their identities as well as perform message authentication over unreliable communication mediums without synchronization and authentication information transmissions. Theoretical analysis and simulation and experiment results show that the proposed method is effective in defending against man-in-the-middle (MITM) attacks and network scanning. It significantly outperforms existing schemes in terms of both security and hopping efficiency.