A method and corresponding network interface device for communicating between devices connected to a LAN includes attempting to communicate between the network devices over an initial subset of the network media wires. If the communication fails, a subsequent subset of media wires is selected. The wires of this subsequent subset differ from the wires of the initial subset. If the attempted communication succeeds, the current subset of network media wires is used as the media over which subsequent network data is transmitted. Attempting to communicate over the media may include sending an initialization sequence such as an Ethernet Auto-negotiate sequence. In one embodiment, the network media is implemented as 8 wires of CAT 5 cabling suitable for use with a Gigabit Ethernet. In this embodiment, any subsequent subsets of the network media wires may consist of 4 of the 8 wires over which 100 Mbps Ethernet operation may occur.