  We study the spin-$\frac{1}{2}$ Kitaev-Heisenberg (KJ) model in a two-leg
ladder. Without a Heisenberg interaction, the Kitaev phase in the ladder model
has Majorana fermions with local Z$_2$ gauge fields, and is usually described
as a disordered phase without any order parameter. Here we prove the existence
of a non-local string order parameter (SOP) in the Kitaev phase which survives
with a finite Heisenberg interaction. The SOP is obtained by relating the
Kitaev ladder, through a non-local unitary transformation, to a one-dimensional
$XY$ chain with an Ising coupling to a dangling spin at every site. This
differentiates the Kitaev phases from other nearby phases including a rung
singlet. Two phases with non-zero SOP corresponding to ferromagnetic and
antiferromagnetic Kitaev interactions are identified. The full phase diagram of
the KJ ladder is determined using exact diagonalization and density matrix
renormalization group methods, which shows a striking similarity to the KJ
model on a two-dimensional honeycomb lattice.
