Fossil cephalopods are frequently encrustated by epibionts; however determining whether encrustation occurred prior to, or post‐mortem the host, and whether the final environment of deposition corresponds to the habitat of encrustation is complex. This paper describes cirripede epibionts, their calcareous bases and their attachment scars on six post‐mortem shells of Nautilus macromphalus Sowerby (1849), collected from deep water off New Caledonia. The cirripedes have left both cemented calcareous bases of Hexelasma and scars associated with bioerosion and discoloration produced by verrucomorph barnacles. Live cirripedes included a Metaverruca recta (Aurivillius, 1898), with articulated opercular plates and organic tissue (on a shell that had been exposed on the sea‐floor for at least 150 years), and specimens of Hexelasma velutinum Hoek, 1913, one of which was partly attached to an internal surface of a shell. The disposition of verrucomorphs indicates that most Nautilus shells were colonized post‐mortem rather than during a floating stage. However, as cirripedes are known to have colonized living Nautilus, some Hexelasma, preserved only as calcareous eroded bases, may represent specimens that settled on a living Nautilus. The degree of bioerosion and discoloration induced by verrucomorph barnacles varies according to the surface preservation of Nautilus shells; traces made by verrucomorphs described here are ellipsoidal and a new ichnotaxon, Anellusichnus ellipticus, is proposed to accommodate them. Importantly, verrucomorphs and other cirripede taxa with membranous bases that were attached to pristine shells may not leave any substantial scars, and thus will be difficult to detect in the fossil record. This article is protected by copyright. All rights reserved.