Non-abelian homology of Lie algebras with coefficients in Lie algebras is constructed and studied, generalising the classical Chevalley-Eilenberg homology of Lie algebras. The relationship between cyclic homology and Milnor cyclic homology of non-commutative associative algebras is established in terms of the long exact non-abelian homology sequence of Lie algebras. Some explicit formulae for the second and the third non-abelian homology of Lie algebras are obtained.