This chapter presents Lucas-Lehmer polynomials and its shifted form which make a series of orthogonal polynomials. The orthogonal polynomials have a big contribution in the approximation theory. We discuss and prove various essential aspects of Lucas-Lehmer polynomials such as the orthogonality, recursive relation and Parseval’s identity. The operational matrix of derivative and integral for LLP is also constructed.