(1) Background: Although olfaction is the predominant sensory modality in rodents, studies focusing on lateralisation of olfactory processing remain scarce, and they are limited to the exploration of brain asymmetries. This study aimed to test whether outbred and inbred mice (NMRI and C57BL/6J mice strains) show nostril-use preference in processing olfactory stimuli differing in terms of emotional valence under unrestrained conditions. (2) Methods: Five odour stimuli were used in the study: vanilla, female urine, garlic, rat, distilled water. We measured the number of times mice used their left or right nostril for each testing session. (3) Results: We here showed that mice preferentially used their right nostril when sniffing attractive stimuli (female urine, vanilla), and their left nostril when sniffing aversive stimuli (rat odour). Results were consistent for both strains. (4) Conclusions: Surprisingly, the results obtained seem opposite to the valence theory assessing that the left and the right hemispheres are dominant in processing stimuli with a positive and a negative valence, respectively. It remains to be determined whether this valence-dependent pattern is specific or not to olfaction in mice. These new findings will be important to better understand how both hemispheres contribute to odour processing in rodents.