A Higher Spin Gravity in five dimensions is constructed. It was shown recently that constructing formally consistent classical equations of motion of higher spin gravities is equivalent to finding a certain deformation of a given higher spin algebra. A strong homotopy algebra encoding the interaction vertices then follows. We propose two different and novel realizations of the deformed higher spin algebra in the case of five dimensions: one in terms of the universal enveloping algebra of $su(2,2)$ and the other by means of oscillator variables. Both the new realizations admit supersymmetric extensions and the $N=8$ case underlies the massless sector of tensionless strings.