We introduce the category of holomorphic string algebroids, whose objects are Courant extensions of Atiyah Lie algebroids of holomorphic principal bundles, as considered by Bressler, and whose morphisms correspond to inner morphisms of the underlying holomorphic Courant algebroids in the sense of Severa. This category provides natural candidates for Atiyah Lie algebroids of holomorphic principal bundles for the (complexified) string group and their morphisms. Our main results are a classification of string algebroids in terms of Cech cohomology, and the construction of a locally complete family of deformations of string algebroids via a differential graded Lie algebra.