  We introduce post-Lie algebra structures on pairs of Lie algebras $(\Lg,\Ln)$
defined on a fixed vector space $V$. Special cases are LR-structures and
pre-Lie algebra structures on Lie algebras. We show that post-Lie algebra
structures naturally arise in the study of NIL-affine actions on nilpotent Lie
groups. We obtain several results on the existence of post-Lie algebra
structures, in terms of the algebraic structure of the two Lie algebras $\Lg$
and $\Ln$. One result is, for example, that if there exists a post-Lie algebra
structure on $(\Lg,\Ln)$, where $\Lg$ is nilpotent, then $\Ln$ must be
solvable. Furthermore special cases and examples are given. This includes a
classification of all complex, two-dimensional post-Lie algebras.
