A system, method and apparatus for multi-lane auto-negotiation over reduced-lane media. Auto-negotiation over an M-lane communication interface can be coordinated with the auto-negotiation over an N-lane communication interface, wherein M > N. A recursive-type auto-negotiation process would begin with the M-lane communication interface and be prevented from completing until the auto-negotiation process over the N-lane communication interface completes.