Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known results about the average-case behaviour of approximation algorithms -- with respect to their running time as well as their performance ratio -- can be unified, though subsuming results about problems being approximable within a certain factor with high probability under the new classes is not straightforward. The structural properties of this framework provide an interesting field of study on their own. We not only define appropriate average-case approximation classes, but also a reduction that preserves approximability within average polynomial time. We show that the class of NP-optimization problems with P-computable input distributions has complete problems with respect to this reduction. The inclusion structure of the average-case approximation classes is investigated. E.g. using a new result by Buhrman, Fortnow and Pavan we are able to show that DistNPO \subseteq Avg_t-PTAS if DistNP \subseteq AvgP.