A New Logistic Map interleaving is the most common method for continuous phase modulation based orthogonal frequency division multiplexing (CPM-OFDM) system over a fading channel. The selection of a "good" interleaver having to express in order that the interleavers are weakly correlated. Interleaver doesn’t involve massive memory to reserve it and a massive bandwidth to communicate in the midst of the transmitter and the receiver, and need to be simple to produce. An efficient chaotic maps randomization (CMR) generates scrambled uncorrelated randomized data can greatly improved the performance of CPM-OFDM system and improved symbol error rate (SER) could be attained. In this study, advise a new one-dimensional chaotic map, the "New Logistic Map (NLM)". Encryption is carried out with logistic map even as a chaotic logistic map interleaving process is used to boost the immunity to noise and fading in communication channel. Furthermore, a evaluation between NLM interleaving and random interleaving is performed in terms of bit error rate(BER).Simulation results shows that the data transmission over wireless channel using propose NLM interleaving is more immune to fading and noise and get better the performance of CPM-OFDM system.