Proteases play a vital role in the removal of proteins, which become damaged due to temperature or oxidative stress. Important to this process in the cyanobacterium Synechocystis sp. PCC6803 is the family of Deg/HtrA proteases; HhoA (sll1679), HhoB (sll1427) and HtrA (slr1204). While previous studies have elucidated the structures of Deg/HtrA proteases from Escherichia coli and from the chloroplast of the higher plant Arabidopsis thaliana, no structural data have been available for any Deg/HtrA protease from cyanobacteria, the evolutionary ancestor of the chloroplast. To gain a deeper insight into the molecular mechanisms and regulation of these proteins we have solved the structure of the Synechocystis HhoA protease in complex with a co-purified peptide by X-ray crystallography. HhoA assembles into stable trimers, mediated by its protease domain and further into a cage-like hexamer by a novel interaction between the PDZ domains of opposing trimers. Each PDZ domain contains two loops for PDZ-PDZ formation: interaction clamp one and two (IC1, IC2). IC1 interacts with IC2 on the opposing PDZ domain and vice versa. Our structure shows a peptide bound to a conserved groove on the PDZ domain and the properties of this pocket suggest that it binds substrate proteins as well as the neo C-termini of cleaved substrates. In agreement with previous studies showing the proteolytic activity of HhoA to be activated by Ca2+ or Mg2+, binding of divalent metal ions to the central channel of the trimer by the L1 activation loop was observed.