Infrared Dark Clouds (IRDCs) are dense molecular clouds seen as extinction features against the bright mid-infrared Galactic background. Millimeter continuum maps toward 38 IRDCs reveal extended cold dust emission to be associated with each of the IRDCs. IRDCs range in morphology from filamentary to compact and have masses of 120 to 16,000 Msun, with a median mass of ~940 Msun. Each IRDC contains at least one compact (<=0.5 pc) dust core and most show multiple cores. We find 140 cold millimeter cores unassociated with MSX 8um emission. The core masses range from 10 to 2,100 Msun, with a median mass of ~120 Msun. The slope of the IRDC core mass spectrum (alpha ~ 2.1 +/- 0.4) is similar to that of the stellar IMF. Assuming that each core will form a single star, the majority of the cores will form OB stars. IRDC cores have similar sizes, masses, and densities as hot cores associated with individual, young high-mass stars, but they are much colder. We therefore suggest that IRDC represent an earlier evolutionary phase in high-mass star formation. In addition, because IRDCs contain many compact cores, and have the same sizes and masses as molecular clumps associated with young clusters, we suggest that IRDCs are the cold precursors to star clusters. Indeed, an estimate of the star formation rate within molecular clumps with similar properties to IRDCs (~2 Msun/yr) is comparable to the global star formation rate in the Galaxy, supporting the idea that all stars may form in such clumps.