In a class of non-Abelian solitonic vortex strings supported in certain
N=2 supersymmetric gauge theories we search for the vortex which can
behave as a critical fundamental string. We identify an appropriate
four-dimensional bulk theory: it has the U(2) gauge group, the
Fayet-Iliopoulos term and four flavors of quark hypermultiplets.
It supports semilocal non-Abelian vortices with the world-sheet theory for
orientational (size) moduli described by the weighted CP(2,2) model. The
latter is superconformal. The overall Virasoro central charge is critical
due to the presence of the internal six-dimensional space. We show that
this non-Abelian vortex behaves as a critical string.