We determine the dimension of the moduli space of non-Abelian vortices in Yang-Mills-Chern-Simons-Higgs theory in 2+1 dimensions for gauge groups $G=U(1)times G$ with $G$ being an arbitrary semi-simple group. The calculation is carried out using a Callias-type index theorem, the moduli matrix approach and a D-brane setup in Type IIB string theory. We prove that the index theorem gives the number of zeromodes or moduli of the non-Abelian vortices, extend the moduli matrix approach to the Yang-Mills-Chern-Simons-Higgs theory and finally derive the effective Lagrangian of Collie and Tong using string theory.