Interoception, the ability to timely and precisely sense changes inside the body, is critical for survival1-4. Vagal sensory neurons (VSNs) form an important body-to-brain connection, navigating visceral organs along the rostral-caudal axis of the body and crossing the surface-lumen axis of organs into appropriate tissue layers5,6. The brain can discriminate numerous body signals through VSNs, but the underlying coding strategy remains poorly understood. Here we show that VSNs code visceral organ, tissue layer and stimulus modality-three key features of an interoceptive signal-in different dimensions. Large-scale single-cell profiling of VSNs from seven major organs in mice using multiplexed projection barcodes reveals a 'visceral organ' dimension composed of differentially expressed gene modules that code organs along the body's rostral-caudal axis. We discover another 'tissue layer' dimension with gene modules that code the locations of VSN endings along the surface-lumen axis of organs. Using calcium-imaging-guided spatial transcriptomics, we show that VSNs are organized into functional units to sense similar stimuli across organs and tissue layers; this constitutes a third 'stimulus modality' dimension. The three independent feature-coding dimensions together specify many parallel VSN pathways in a combinatorial manner and facilitate the complex projection of VSNs in the brainstem. Our study highlights a multidimensional coding architecture of the mammalian vagal interoceptive system for effective signal communication.