Devices and methods provide Media Access Control (MAC) address randomization support for multi-link devices. A multi-link client device transmits an Identifiable Random Media Access Control (IRM) address of the multi-link client device to a network device. The multi-link client device generates one or more wireless frames indicating the IRM address as a physical address. The IRM address in each wireless frame identifies at least one station of the multi-link client device. The multi-link client device transmits the wireless frame(s) to the network device. The network device receives and stores a first IRM address of the multi-link client device. The network device receives at least one wireless frame indicating a second IRM address as a physical address. The network device recognizes at least one station of the multi-link client device based on a match of the second IRM address with the first IRM address.