The cyanobacterium Anabaena (Nostoc) PCC 7120 responds to starvation for nitrogen compounds by differentiating approximately every 10th cell in the filament into nitrogen-fixing cells called heterocysts. Heterocyst formation is subject to complex regulation, which involves an unusual response regulator PatA that contains a CheY-like phosphoacceptor (receiver, REC) domain at its C-terminus. PatA-like response regulators are widespread in cyanobacteria; one of them regulates phototaxis in Synechocystis PCC 6803. Sequence analysis of PatA revealed, in addition to the REC domain, a previously undetected, conserved domain, which we named PATAN (after PatA N-terminus), and a potential helix-turn-helix (HTH) domain. PATAN domains are encoded in a variety of environmental bacteria and archaea, often in several copies per genome, and are typically associated with REC, Roadblock and other signal transduction domains, or with DNA-binding HTH domains. Many PATAN domains contain insertions of a small additional domain, termed alpha-clip, which is predicted to form a four-helix bundle. PATAN domains appear to participate in protein-protein interactions that regulate gliding motility and processes of cell development and differentiation in cyanobacteria and some proteobacteria, such as Myxococcus xanthus and Geobacter sulfurreducens.