In this paper, we examine the conditions under which a higher-spin string theory can be quantized. The quantizability is crucially dependent on the way in which the matter currents are realized at the classical level. In particular, we construct classical realizations for the W2,s algebra, which is generated by a primary spin-s current in addition to the energy-momentum tensor, and discuss the quantization for s≤8. From these examples we see that quantum BRST operators can exist even when there is no quantum generalization of the classical W2,s algebra. Moreover, we find that there can be several inequivalent ways of quantizing a given classical theory, leading to different BRST operators with inequivalent cohomologies. We discuss their relation to certain minimal models. We also consider the hierarchical embeddings of string theories proposed recently by Berkovits and Vafa, and show how the already known W strings provide examples of this phenomenon. Attempts to find higher-spin fermionic generalizations lead us to examine whether classical BRST operators for [Formula: see text](n odd) algebras can exist. We find that even though such fermionic algebras close up to null fields, one cannot build nilpotent BRST operators, at least of the standard form.