Microbes are the engines driving the elemental cycles. In order to interact with their environment and the community, microbes secrete proteins into the environment (known collectively as the secretome), where they remain active for prolonged periods of time. Despite the environmental relevance of microbes and the vast quantities of marine prokaryotic sequences available, our knowledge of the marine secretome remains limited due to the available in silico methods for the study of secreted proteins, which are not suited to their use in large datasets due to their low throughput. An alternative and potentially better approach to characterise the secretome is to combine modern machine learning tools with the evolutionary adaptation changes of the proteome to the marine environment. In this study, we found and described adaptations of marine extracellular proteins, which vary between phyla, resulting in differences in ATP costs, amino acid composition and nitrogen and sulphur content. With these adaptations in mind, we developed ‘Ayu’, a machine prediction tool that does not employ homology-based predictors (as current methods do) and achieves better performance than current state-of-the-art software at a fraction of the time. When applied to oceanic samples (Tara Oceans dataset), our method was able to recover more than double the proteins compared to the most widely used method to identify secreted proteins, indicating that more than half of secreted proteins are presently unconsidered in current secrtome analysis. The application of this powerful novel to open ocean samples allowed to better characterise the real composition of the marine secretome, allowing for a better recognition and understanding of the secretome in marine ecosystems.