Chemotaxis allows cells to sense and respond to their environment. In Bacteria, stimuli are detected by arrays of chemoreceptors that relay the signal to a two‐component regulatory system. These arrays take the form of highly stereotyped super‐lattices comprising hexagonally packed trimers‐of‐receptor‐dimers networked by rings of histidine kinase and coupling proteins. This structure is conserved across chemotactic Bacteria, and between membrane‐bound and cytoplasmic arrays, and gives rise to the highly cooperative, dynamic nature of the signalling system. The chemotaxis system, absent in eukaryotes, is also found in Archaea, where its structural details remain uncharacterized. Here we provide evidence that the chemotaxis machinery was not present in the last archaeal common ancestor, but rather was introduced in one of the waves of lateral gene transfer that occurred after the branching of Eukaryota but before the diversification of Euryarchaeota. Unlike in Bacteria, the chemotaxis system then evolved largely vertically in Archaea, with very few subsequent successful lateral gene transfer events. By electron cryotomography, we find that the structure of both membrane‐bound and cytoplasmic chemoreceptor arrays is conserved between Bacteria and Archaea, suggesting the fundamental importance of this signalling architecture across diverse prokaryotic lifestyles.