We investigate the question: when is a higher-rank graph C*-algebra approximately finite-dimensional? We prove that the absence of an appropriate higher-rank analogue of a cycle is necessary. We show that it is not in general sufficient, but that it is sufficient for higher-rank graphs with finitely many vertices. We give a detailed description of the structure of the C*-algebra of a row-finite locally convex higher rank graph with finitely many vertices. Our results are also sufficient to establish that if the C*-algebra of a higher-rank graph is AF, then its every ideal must be gauge-invariant. We prove that for a higher-rank graph C*-algebra to be AF it is necessary and sufficient for all the corners determined by vertex projections to be AF. We close with a number of examples which illustrate why our question is so much more difficult for higher-rank graphs than for ordinary graphs.