Symbiosis is an important driving force in metazoan evolution and the study of ancient lineages can provide an insight into the influence of symbiotic associations on morphological and physiological adaptations. In the 'living fossil' Nautilus, bacterial associations are found in the highly specialized pericardial appendage. This organ is responsible for most of the excretory processes (ultrafiltration, reabsorption and secretion) and secretes an acidic ammonia-rich excretory fluid. In this study, we show that Nautilus macromphalus pericardial appendages harbour a high density of a beta-proteobacterium and a coccoid spirochaete using transmission electron microscopy, comparative 16S rRNA sequence analysis and fluorescence in situ hybridization (FISH). These two bacterial phylotypes are phylogenetically distant from any known bacteria, with ammonia-oxidizing bacteria as the closest relatives of the beta-proteobacterium (above or equal to 87.5% sequence similarity) and marine Spirochaeta species as the closest relatives of the spirochaete (above or equal to 89.8% sequence similarity), and appear to be specific to Nautilus. FISH analyses showed that the symbionts occur in the baso-medial region of the pericardial villi where ultrafiltration and reabsorption processes take place, suggesting a symbiotic contribution to the excretory metabolism.