  In this paper we work out some basic results concerning heterotic string
compactifications on stacks and, in particular, gerbes. A heterotic string
compactification on a gerbe can be understood as, simultaneously, both a
compactification on a space with a restriction on nonperturbative sectors, and
also, a gauge theory in which a subgroup of the gauge group acts trivially on
the massless matter. Gerbes admit more bundles than corresponding spaces, which
suggests they are potentially a rich playground for heterotic string
compactifications. After we give a general characterization of heterotic
strings on stacks, we specialize to gerbes, and consider three different
classes of `building blocks' of gerbe compactifications. We argue that
heterotic string compactifications on one class is equivalent to
compactification of the same heterotic string on a disjoint union of spaces,
compactification on another class is dual to compactifications of other
heterotic strings on spaces, and compactification on the third class is not
perturbatively consistent, so that we do not in fact recover a broad array of
new heterotic compactifications, just combinations of existing ones. In
appendices we explain how to compute massless spectra of heterotic strings on
stacks, derive some new necessary conditions for a heterotic string on a stack
or orbifold to be well-defined, and also review some basic properties of
bundles on gerbes.
