A twisted covariant formulation of noncommutative self-dual gravity is presented. The formulation for constructing twisted noncommutative Yang-Mills theories is used. It is shown that the noncommutative torsion is solved at any order of the $theta$-expansion in terms of the tetrad and some extra fields of the theory. In the process the first order expansion in $theta$ for the Plebanski action is explicitly obtained.