This article is the companion of [G. Tabuada, Postnikov towers, k-invariants and obstruction theory for DC categories, J. Algebra, in press]. By inspiring ourselves in Andre-Quillen's work [D. Quillen, On the (co)-homology of commutative rings, in: Proc. Sympos. Pure Math., vol. 17, Amer. Math. Soc., 1970, pp. 65-87], we develop a non-commutative Andre-Quillen cohomology theory for differential graded categories. As in the classical case of commutative rings, there are derivations, square-zero extension, (non-commutative) cotangent complexes. We prove that our cohomology theory satisfies transitivity, a Mayer-Vietoris's property, and is the natural algebraic setting for the k-invariants and obstruction classes constructed in [G. Tabuada, Postnikov towers. k-invariants and obstruction theory for DG categories, J. Algebra, in press]. (C) 2009 Elsevier Inc. All rights reserved.