We constructed a 1,257-marker, high-density genetic map of Brassica oleracea spanning 703 cM in nine linkage groups, designated LG1-LG9. It was developed in an F2 segregating population of 143 individuals obtained by crossing double haploid plants of broccoli "Early-Big" and cauliflower "An-Nan Early". These markers are randomly distributed throughout the map, which includes a total of 1,062 genomic SRAP markers, 155 cDNA SRAP markers, 26 SSR markers, 3 broccoli BAC end sequences and 11 known Brassica genes: BoGSL-ALK, BoGSL-ELONG, BoGSL-PROa, BoGSL-PROb, BoCS-lyase, BoGS-OH, BoCYP79F1, BoS-GT (glucosinolate pathway), BoDM1 (resistance to downy mildew), BoCALa, BoAP1a (inflorescence architecture). BoDM1 and BoGSL-ELONG are linked on LG 2 at 0.8 cM, making it possible to use the glucosinolate gene as a marker for the disease resistance gene. By QTL analysis, we found three segments involved in curd formation in cauliflower. The map was aligned to the C genome linkage groups and chromosomes of B. oleracea and B. napus, and anchored to the physical map of A. thaliana. This map adds over 1,000 new markers to Brassica molecular tools.