Coral aggregate has been widely used for island construction because of its local availability. However, the addition of coral aggregate exaggerates the brittle nature of cement-based materials under dynamic loading. In this study, polyvinyl alcohol (PVA) fiber was used to improve dynamic mechanical behavior of seawater coral mortars (SCMs). The effects of coral aggregate and PVA fiber on the workability, static mechanical strengths, and dynamic mechanical behavior of fiber-reinforced SCMs were investigated. Results showed that the workability of the SCM decreased with increasing coral aggregate replacement rate and PVA fiber content. Mechanical strengths of the SCM increased with increasing PVA fiber content, but decreased with increasing coral aggregate replacement rate. Dynamic mechanical behavior at varying coral aggregate replacement rates was analyzed by combining dynamic mechanical analysis and micro-scale elastic modulus experiment. With increasing coral aggregate replacement rate, the storage modulus, loss factor, and elastic modulus of the interfacial transition zone in the SCM decreased. Nevertheless, with the incorporation of PVA fibers (1 vol.%), the storage modulus and loss factor were improved dramatically by 151.9 and 73.3%, respectively, compared with the reference group. Therefore, fiber-reinforced coral mortars have a great potential for use in island construction, owing to the excellent anti-vibrational performance.