Music is known to induce emotions and activate associated memories, including musical memories. In adults, it is well known that music activates both working memory and limbic networks. We have recently discovered that as early as during the newborn period, familiar music is processed differently from unfamiliar music. The present study evaluates music listening effects at the brain level in newborns, by exploring the impact of familiar or first-time music listening on the subsequent resting-state functional connectivity in the brain. Using a connectome-based framework, we describe resting-state functional connectivity (RS-FC) modulation after music listening in three groups of newborn infants, in preterm infants exposed to music during their neonatal-intensive-care-unit (NICU) stay, in control preterm, and full-term infants. We observed modulation of the RS-FC between brain regions known to be implicated in music and emotions processing, immediately following music listening in all newborn infants. In the music exposed group, we found increased RS-FC between brain regions known to be implicated in familiar and emotionally arousing music and multisensory processing, and therefore implying memory retrieval and associative memory. We demonstrate a positive correlation between the occurrence of the prior music exposure and increased RS-FC in brain regions implicated in multisensory and emotional processing, indicating strong engagement of musical memories; and a negative correlation with the Default Mode Network, indicating disengagement due to the aforementioned cognitive processing. Our results describe the modulatory effect of music listening on brain RS-FC that can be linked to brain correlates of musical memory engrams in preterm infants.