The development of new approaches to prevent microbial surface adhesion and biofilm formation is an emerging need following the growing understanding of the impact of biofilm-related infections on human health. Staphylococcus epidermidis, with its ability to form biofilm and colonize biomaterials, represents the most frequent causative agent involved in infections of medical devices. In the research of new anti-biofilm agents against S. epidermidis biofilm, Antarctic marine bacteria represent an untapped reservoir of biodiversity. In the present study, the attention was focused on Psychrobacter sp. TAE2020, an Antarctic marine bacterium that produces molecules able to impair the initial attachment of S. epidermidis strains to the polystyrene surface. The setup of suitable purification protocols allowed the identification by NMR spectroscopy and LC-MS/MS analysis of a protein–polysaccharide complex named CATASAN. This complex proved to be a very effective anti-biofilm agent. Indeed, it not only interferes with cell surface attachment, but also prevents biofilm formation and affects the mature biofilm matrix structure of S. epidermidis. Moreover, CATASAN is endowed with a good emulsification activity in a wide range of pH and temperature. Therefore, its use can be easily extended to different biotechnological applications.