Abstract For a fixed integer r2, the Kr-packing problem is to find the maximum number of pairwise vertex-disjointKrs (complete graphs on r vertices) in a given graph. The Kr-factor problem asks for the existence of a partition of the vertex set of a graph into Krs. The Kr-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r3 it is known that for r3 the Kr-factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the Kr-packing problem on restricted classes of graphs. We first prove that for r3 the Kr-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K3-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K3-packing and the Kr-factor problems on split graphs (this is interesting in light of the fact that Kr-packing becomes NP-complete on split graphs for r4), and for the Kr-packing problem on cographs.