Biotin-dependent carboxylases are widely distributed in nature and have important functions in many cellular processes. These enzymes share a conserved biotin carboxylase (BC) component, which catalyzes the ATP-dependent carboxylation of biotin using bicarbonate as the donor. Despite the availability of a large amount of biochemical and structural information on BC, the molecular basis for its catalysis is currently still poorly understood. We report here the crystal structure at 2.0 A resolution of wild-type Escherichia coli BC in complex with its substrates biotin, bicarbonate, and Mg-ADP. The structure suggests that Glu(296) is the general base that extracts the proton from bicarbonate, and Arg(338) is the residue that stabilizes the enolate biotin intermediate in the carboxylation reaction. The B domain of BC is positioned closer to the active site, leading to a 2-A shift in the bound position of the adenine nucleotide and bringing it near the bicarbonate for catalysis. One of the oxygen atoms of bicarbonate is located in the correct position to initiate the nucleophilic attack on ATP to form the carboxyphosphate intermediate. This oxygen is also located close to the N1' atom of biotin, providing strong evidence that the phosphate group, derived from decomposition of carboxyphosphate, is the general base that extracts the proton on this N1' atom. The structural observations are supported by mutagenesis and kinetic studies. Overall, this first structure of BC in complex with substrates offers unprecedented insights into the molecular mechanism for the catalysis by this family of enzymes.