Methods currently available to estimate the post-mortem submerged interval (PMSI) of cadavers in water suffer from poor accuracy, being mostly based on morphological examination of the remains. Proteins present within bones have recently attracted more attention from researchers interested in the estimation of the post-mortem interval (PMI) in terrestrial environments. Despite the great potential of proteomic methods for PMI estimation, their application to aquatic environments has not yet been explored. In this study, we examined whether four different types of aquatic environment affected the proteome of mice bones with increasing PMSIs. Results showed that both increasing PMSIs and different types of water can influence the proteome. In particular, two muscle proteins, creatine kinase M type and glycogen phosphorylase, were found more abundant in mice decomposed in saltwater compared to the other environments. Furthermore, coagulation factor VII was deamidated only in submerged samples and not in terrestrial controls. Finally, fetuin-A was significantly more deamidated in pond water compared to the other aquatic environments. Overall, this study identified novel potential biomarker candidates that would be useful for the estimation of the PMSI and for the characterization of the type of water involved in criminal investigations.