The Great Nebula in Carina is a superb location in which to study the physics of violent massive star-formation and the resulting feedback effects, including cloud dispersal and triggered star-formation. In order to reveal the cold dusty clouds in the Carina Nebula complex, we used the Large APEX Bolometer Camera LABOCA at the APEX telescope to map a 1.25 deg x 1.25 deg (= 50 x 50 pc^2) region at 870 micrometer. From a comparison to Halpha images we infer that about 6% of the 870 micrometer flux in the observed area is likely free-free emission from the HII region, while about 94% of the flux is very likely thermal dust emission. The total (dust + gas) mass of all clouds for which our map is sensitive is ~ 60 000 Msun, in good agreement with the mass of the compact clouds in this region derived from 13CO line observations. We generally find good agreement in the cloud morphology seen at 870 micrometer and the Spitzer 8 micrometer emission maps, but also identify a prominent infrared dark cloud. Finally, we construct a radiative transfer model for the Carina Nebula complex that reproduces the observed integrated spectral energy distribution reasonably well. Our analysis suggests a total gas + dust mass of about 200000 Msun in the investigated area; most of this material is in the form of molecular clouds, but a widely distributed component of (partly) atomic gas, containing up to ~ 50% of the total mass, may also be present. Currently, only some 10% of the gas is in sufficiently dense clouds to be immediately available for future star formation, but this fraction may increase with time owing to the ongoing compression of the strongly irradiated clouds and the expected shockwaves of the imminent supernova explosions.