Symbiosis is increasingly recognized as being an important component in marine systems, and many such relationships are initiated when free-swimming larvae of one partner settle and become sedentary on a host partner. Therefore, several crucial questions emerge such as the larva’s mechanism of locating a host, selection of substratum and finally settlement on the surface of its future partner. Here, we investigated these mechanisms by studying how larvae of the fire coral-associated barnacle Wanella milleporae move, settle and establish symbiosis with their host, Millepora tenera. Cyprids of W. milleporae possess a pair of specialized antennules with bell-shaped attachment discs that enable them to explore and settle superficially on the hostile surface of the fire coral. Intriguingly, the stinging polyps of the fire coral remain in their respective pores when the cyprids explore the fire coral surface. Even when cyprids come into contact with the nematocysts on the extended stinging polyps during the exploratory phase, no immobilization effects against the cyprids were observed. The exploratory phase of Wanella cyprids can be divided into a sequence of wide searching (large step length and high walking speed), close searching (small step length and low speed) and inspection behavior, eventually resulting in permanent settlement and metamorphosis. After settlement, xenogeneic interactions occur between the fire coral and the newly metamorphosed juvenile barnacle. This involved tissue necrosis and regeneration in the fire coral host, leading to a callus ring structure around the juvenile barnacle, enhancing survival rate after settlement. The complex exploratory and settlement patterns and interactions documented here represent a breakthrough in coral reef symbiosis studies to show how invertebrates start symbiosis with fire corals.