The structure and organization of 470 histidine biosynthetic genes from 47 different proteobacteria were combined with phylogenetic inference to investigate the mechanisms responsible for assembly of the his pathway and the origin of his operons. Data obtained in this work showed that a wide variety of different organization strategies of his gene arrays exist and that some his genes or entire his operons are likely to have been horizontally transferred between bacteria of the same or different proteobacterial branches. We propose a "piecewise" model for the origin and evolution of proteobacterial his operons, according to which the initially scattered his genes of the ancestor of proteobacteria coded for monofunctional enzymes (except possibly for hisD) and underwent a stepwise compacting process that reached its culmination in some gamma-proteobacteria. The initial step of operon buildup was the formation of the his "core," a cluster consisting of four genes (hisBHAF) whose products interconnect histidine biosynthesis to both de novo synthesis of purine metabolism and that occurred in the common ancestor of the alpha/beta/gamma branches, possibly after its separation from the epsilon one. The following step was the formation of three mini-operons (hisGDC, hisBHAF, hisIE) transcribed from independent promoters, that very likely occurred in the ancestor of the beta/gamma-branch, after its separation from the alpha one. Then the three mini-operons joined together to give a compact operon. In most gamma-proteobacteria the two fusions involving the gene pairs hisN-B and hisI-E occurred. Finally the gamma-proteobacterial his operon was horizontally transferred to other proteobacteria, such as Campylobacter jejuni. The biological significance of clustering of his genes is also discussed.