This study introduces higher order Mersenne and Gaussian higher order Mersenne polynomials. We present their relation with the classical Mersenne and Gaussian Mersenne polynomials, respectively. We find the Binet’s formula for both. We obtain Halton’s, Honsberger’s, Catalan’s, Vajda’s, Cassini’s, Gelin-Cesaro’s, and d’Ocagne identities followed by sum formulas in arithmetic indices. We present generating functions for both and give the matrix representation for higher order Mersenne polynomials. Further, we define Hadamard-type Fibonacci-Higher order Mersenne p-sequences, investigate some properties and apply these new sequences in the Affine-Hill cipher to generate keys using an elliptic curve.