Cannulae are tubular protein filaments that accumulate on the extracellular surface of the hyperthermophilic archaeon during cell division. Cannulae have been postulated to act as a primitive extracellular matrix through which cells could communicate or exchange material, although their native biological function remains obscure. Here, we report cryoEM structural analyses of cannulae and of protein assemblies derived from recombinant cannula-like proteins. Three-dimensional reconstructions of cannulae revealed that the structural interactions between protomers in the native and recombinant filaments were based on donor strand complementation, a form of non-covalent polymerization in which a donor β-strand from one subunit is inserted into an acceptor groove in a β-sheet of a neighboring subunit. Donor strand complementation in cannulae is reinforced through calcium ion coordination at the interfaces between structural subunits in the respective assemblies. While donor strand complementation occurs during the assembly of chaperone-usher pili, this process requires the participation of accessory proteins that are localized in the outer membrane. In contrast, we demonstrate that calcium ions can induce assembly of cannulae in the absence of other co-factors. Crystallographic analysis of a recombinant cannula-like protein monomer provided evidence that calcium ion binding primes the precursor for donor strand invasion through unblocking of the acceptor groove. Bioinformatic analysis suggested that structurally homologous cannula-like proteins occurred within the genomes of other hyperthermophilic archaea and were encompassed within the TasA superfamily of biomatrix proteins. CryoEM structural analyses of tubular filaments derived from assembly of a recombinant cannula-like protein from an uncultured species revealed a common mode of assembly to the cannulae, in which donor strand complementation and calcium ion binding stabilized longitudinal and lateral assembly in tubular 2D sheets.