The scleractinian coral Lophelia pertusa has been the focus of deep-sea research since the recognition of the vast extent of coral reefs in North Atlantic waters two decades ago, long after their existence was mentioned by fishermen. These reefs where shown to provide habitat, concentrate biomass and act as feeding or nursery grounds for many species, including those targeted by commercial fisheries. Thus, the attention given to this cold-water coral (CWC) species from researchers and the wider public has increased. Consequently, new research programs triggered research to determine the full extent of the corals geographic distribution and ecological dynamics of “Lophelia reefs”. The present study is based on a systematic standardised sampling design to analyse the distribution and coverage of CWC reefs along European margins from the Bay of Biscay to Iceland. Based on Remotely Operated Vehicle (ROV) image analysis, we report an almost systematic occurrence of Madrepora oculata in association with L. pertusa with similar abundances of both species within explored reefs, despite a tendency of increased abundance of L. pertusa compared to M. oculata toward higher latitudes. This systematic association occasionally reached the colony scale, with “twin” colonies of both species often observed growing next to each other when isolated structures were occurring off-reefs. Finally, several “false chimaera” were observed within reefs, confirming that colonial structures can be “coral bushes” formed by an accumulation of multiple colonies even at the inter-specific scale, with no need for self-recognition mechanisms. Thus, we underline the importance of the hitherto underexplored M. oculata in the Eastern Atlantic, re-establishing a more balanced view that both species and their yet unknown interactions are required to better elucidate the ecology, dynamics and fate of European CWC reefs in a changing environment.