This paper presents flexible NdFeB-PDMS composite magnets with tunable magnetic and mechanical properties optimized for applications in corrosive marine environments. The magnetic and mechanical properties are studied for different NdFeB powder concentrations and the performance of the magnetic composites for different exposure times to sea water investigated systematically. The remanence and saturation magnetizations could be tailored by the powder concentration, whereby up to 70 wt% concentration could be employed without compromising the integrity of the magnets. The elastic modulus of the composite magnets is about 105 times lower than the one of a bulk permanent magnet. This ensures a high bending flexibility, which allows the magnets to be attached to curved surfaces as illustrated for a giant clam, crab, and turtle. At the same time, the weight of the composite magnets is reduced by a factor of about 10, which poses less burden to animals’ natural free movement. Without a protective layer, the composite magnets lose more than 50% of their magnetization after 51 days in seawater. However, the durability of the composite magnets has been improved considerably by using polymer coatings. Parylene C is the most effective for this, providing corrosion resistance, flexibility, and enhanced biocompatibility. Parylene C films of 2 and 4 μm thicknesses provided excellent protection of the magnetic composite in corrosive aqueous environments for 65 and 82 days, respectively. By combining the composite magnets with tunnel magnetoresistance sensors, a magnetic animal monitoring system is established that is used to track the behavior of giant clam, crab, and turtle.