We revisit the higher spin extensions of the anti de Sitter algebra in four dimensions that incorporate internal symmetries and admit representations that contain fermions, classified long ago by Konstein and Vasiliev. We construct the dS 4 , Euclidean and Kleinian version of these algebras, as well as the corresponding fully nonlinear Vasiliev type higher spin theories, in which the reality conditions we impose on the master fields play a crucial role. The N = 2 supersymmetric higher spin theory in dS 4 , on which we elaborate further, is included in this class of models. A subset of the Konstein-Vasiliev algebras are the minimal higher spin extensions of the AdS 4 superalgebra with osp(4|N) with N = 1, 2, 4 mod 4, whose R-symmetry can be realized using fermionic oscillators. We tensor these algebras with appropriate internal symmetry algebras, namely u(n) for N = 2 mod 4 and so(n) or usp(n) for N = 1, 4 mod 4. We show that the N = 3 mod 4 higher spin algebras are isomorphic to those with N = 4 mod 4. We describe the fully nonlinear higher spin theories based on these algebras, including the coupling between the adjoint and twisted-adjoint master fields. We elaborate further on N = 6 the model in AdS 4 , and provide two equivalent descriptions one of which exhibits manifestly its relation to the N = 8 model. 2013 IOP Publishing Ltd.