In the framework of EU-project ORPHEE, some innovative solid fuel formulations for hybrid rocket propulsion were manufactured and tested in order to overcome the shortcoming of very low fuel regression rates, typical of conventional hybrid rocket fuels. Firing tests were perfomed in a 2D slab burner implemented at SPLab (Space Propulsion Laboratory of Politecnico di Milano). Nano-Al powders and a metal hydride (Magnesium hydride (MgH2)) were used as fillers in paraffin matrices. The highest regression rates were found for the Solid Wax (SW) composition, added with 5% MgH2 mass fraction. At 350 kg/m2s oxygen mass flux, the measured regression rate, averaged in space and time, was 2.5 mm/s, which is approximately five times higher than that of the pure HTPB composition, taken as baseline reference fuel. Compositions added with nano-sized Aluminum powders were compared with those added with MgH2, using gel or solid wax. A rheological investigation and a mechanical characterization were performed, in order to explain the dependence of the regression rate on the nature and size of the metal powder, the viscosity of the paraffin melted layer, the thermodynamic properties of the different paraffins considered in this work.