Techniques are provided for performing discovery in a Fiber Channel over Ethernet (FCoE) network. An FCF discovers other FCoE Forwarders (FCFs) connected to its network segment by transmitting a solicitation message to the multicast MAC address “All-FCF-MACs”. All FCFs receive packets with this multicast MAC address including the solicitation message that announces the presence of the FCF. Each FCF replies with a unicast advertisement message that provides the new FCF with a MAC address of the responding FCF. The FCF builds a list of the FCFs available on its network segment and may then establish a virtual link with one or more of the FCFs through an exchange link parameter (ELP) exchange.