We present a classification of bilinear Majorana representations for spin-S operators, based on the real irreducible matrix representations of SU(2). We identify two types of such representations: While the first type can be straightforwardly mapped onto standard complex fermionic representations of spin-S operators, the second type realizes spin amplitudes S=s(s+1)/4 with s∈N and can be considered particularly efficient in representing spins via fermions. We show that for s=1 and s=2 this second type reproduces known spin-1/2 and spin-3/2 Majorana representations and we prove that these are the only bilinear Majorana representations that do not introduce any unphysical spin sectors. While for s>2, additional unphysical spin spaces are unavoidable they are less numerous than for more standard complex fermionic representations and carry comparatively small spin amplitudes. We apply our Majorana representations to exactly solvable small spin clusters and confirm that their low-energy properties remain unaffected by unphysical spin sectors, making our representations useful for auxiliary-particle based methods.