The moduli space NK of infinitesimal deformations of a nearly Kahler structure on a compact 6-dimensional manifold is described by a certain eigenspace of the Laplace operator acting on co-closed primitive (1,1) forms. Using the Hermitian Laplace operator and some representation theory, we compute the space NK on all 6-dimensional homogeneous nearly Kahler manifolds. It turns out that the nearly Kahler structure is rigid except for the flag manifold F(1,2)=SU_3/T^2, which carries an 8-dimensional moduli space of infinitesimal nearly Kahler deformations, modeled on the Lie algebra su_3 of the isometry group.