Bit-interleaved coded modulation with iterative decoding (BICM-ID) are suitable for continuous fading channels. In addition, BICM-ID using differential encoding can avoid the rate loss due to pilot symbols. Conventional differential encoding for uncoded modulation was used for BICM-ID. In this paper, we propose new differential encoding of 16APSK (amplitude and phase-shift keying) signals for BICM-ID. We first derive the probability of receiving signals conditioned on the transmission of input bits of general differential encoding. After that, we propose a new algorithm to optimize differential encoding for BICM-ID, and use it to find the differential encoding of 16APSK. Besides, code searches for the proposed differential encoding are performed. Simulation results show that the proposed differential encoding has better error performance than conventional differential encoding, and the searched new codes can further improve error performance.