  Non-Abelian strings for an Einstein-Yang-Mills-Higgs theory are explicitly
constructed. We consider N_f Higgs fields in the fundamental representation of
the U(1)xSU(N_c) gauge group in order to have a color-flavor SU(N_c) group
remaining unbroken. Choosing a suitable ansatz for the metric, Bogomol'nyi-like
first order equations are found and rotationally symmetric solutions are
proposed. In the N_f = N_c case, solutions are local strings and are shown to
be truly non-Abelian by parameterizing them in terms of orientational
collective coordinates. When N_f > N_c, the solutions correspond to semilocal
strings which, beside the orientational degrees of freedom, acquire additional
collective coordinates parameterizing their transverse size. The low-energy
effective theories for the correspondent moduli are found, showing that all
zero modes are normalizable in presence of gravity, even in the semilocal case.
