In last years, low-dimensional and high-dimensional chaotic systems have been implemented in cryptography. The efficiency and performance of these nonlinear systems play an important role in limited hardware implementations. In this context, low-dimensional chaotic systems are more attractive than high-dimensional chaotic systems to produce the pseudorandom key stream used for encryption purposes. Although low-dimensional chaotic maps present some security disadvantages when they are used in cryptography, they are highly attractive due its simple structure, discrete nature, less arithmetic operations, high output processing, and relatively easy to implement in a digital system. In this paper, we proposed both a pseudorandomly enhanced logistic map (PELM) and its application in a novel pseudorandom number generator (PRNG) algorithm, which produces pseudorandom stream with excellent statistical properties. The proposed PELM is compared with logistic map by using histograms and Lyapunov exponents to show its higher benefits in pseudorandom number generator. In contrast to recent schemes in the literature, we present a comprehensive security analysis over the proposed pseudorandom number generator based on pseudorandomly enhanced logistic map (PRNG-PELM) from a cryptographic point of view to show its potential use in secure communications. In addition, the randomness of the PRNG-PELM is verified with the most complete random test suit of National Institute of Standards and Technology (NIST 800-22) and with TestU01. Based on security results, few arithmetic operations required, and high output rate, the proposed PRNG-PELM scheme can be implemented in secure encryption applications, even in embedded systems with limited hardware resources.