In the model legume Medicago truncatula, two mutants, sickle and sunn, exhibit morphologically and genetically distinct hypernodulation phenotypes. However, efforts to isolate the single recessive and single semidominant genes for sickle and sunn, respectively, by map-based cloning have so far been unsuccessful, partly due to the absence of clones that enable walks from linked marker positions. To help resolve these difficulties, a new bacterial artificial chromosome (BAC) library was constructed using BamHI-digested genomic fragments. A total of 23,808 clones were collected from ligation mixtures prepared with double-size-selected high-molecular-weight DNA. The average insert size was 116 kb based on an analysis of 88 randomly selected clones using NotI digestion and pulsed-field gel electrophoresis. About 18.5% of the library clones lacked inserts. The frequency of the BAC clones carrying chloroplast or mitochondrial DNA was 0.98% and 0.03%, respectively. The library represented approximately 4.9 haploid M. truncatula genomes. Hybridization of the BAC clone filters with a $C_{0}t-l$ DNA probe revealed that approximately 37% of the clones likely carried repetitive sequence-enriched DNA. An ordered array of pooled BAC DNA was screened by polymerase chain reactions using 13 sequence-characterized molecular markers that belonged to the eight linkage groups. Except for two markers, one to five positive BAC clones were obtained per marker. Accordingly, the sickle- and sunn-linked BAC clones identified herein will be useful for the isolation of these biotechnologically important genes. The new library will also provide clones that fill the gaps between preexisting BAC contigs, facilitating the physical mapping and genome sequencing of M. truncatula.