We use a multi-color classification method introduced by Wolf, Meisenheimer & Roeser (2000) to reliably identify stars, galaxies and quasars in the up to 16-dimensional color space provided by the filter set of the Calar Alto Deep Imaging Survey (CADIS). The samples of stars, galaxies and quasars obtained this way have been used for dedicated studies published in separate papers. The classification is good enough to detect quasars rather completely and efficiently without confirmative spectroscopy. The multi-color redshifts are accurate enough for most statistical applications, e.g. evolutionary studies of the galaxy luminosity function. We characterize our current dataset on the CADIS 1h-, 9h- and 16h-fields. Using Monte-Carlo simulations we model the classification performance expected for CADIS. We present a summary of the classification results and discuss unclassified objects. More than 99% of the whole catalog sample at R<22 (more than 95% at R<23) are successfully classified matching the expectations derived from the simulations. A small number of peculiar objects challenging the classification are discussed in detail. Spectroscopic observations are used to check the reliability of the multi-color classification (6 mistakes among 151 objects with R<24). We also determine the accuracy of the multi-color redshifts which are rather good for galaxies (sigma_z = 0.03) and useful for quasars. We find the classification performance derived from the simulations to compare well with results from the real survey. Finally, we locate areas for potential improvement of the classification.