In this paper, we examine the conditions under which a higher-spin string theory can be quantised. The quantisability is crucially dependent on the way in which the matter currents are realised at the classical level. In particular, we construct classical realisations for the $W_{2,s}$ algebra, which is generated by a primary spin-$s$ current in addition to the energy-momentum tensor, and discuss the quantisation for $sle8$. From these examples we see that quantum BRST operators can exist even when there is no quantum generalisation of the classical $W_{2,s}$ algebra. Moreover, we find that there can be several inequivalent ways of quantising 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 generalisations lead us to examine the whether classical BRST operators for $W_{2,{nover 2}}$ ($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.