The utilization of coral aggregate concrete (CAC) in marine construction has drawn the attention of engineers and researchers in recent years. Due to the high content of chloride in CAC induced by coral aggregates and sea water, reinforcing CAC with traditional material, i.e., steel, can cause serious corrosion-related durability problems. Replacing steel with corrosion-resistant fiber-reinforced polymer (FRP) has been considered a promising solution. This paper provides insight into the bond behavior between CAC and FRP bars. In total 30 pull-out tests were conducted. The investigated variables included the concrete matrix, FRP bar type, bar diameter, and thickness of concrete cover. Based on the test results, discussions on the bond failure modes, influencing factors of bond strength and bond stress-slip relationship were presented. For splitting failure mode and pullout failure mode, empirical bond stress-slip models were proposed respectively. Adopting the failure criterion of CAC proposed in a previous study, a mechanical model for bond strength under pullout failure mode was developed. Comparisons with test results validated that the proposed models provide reasonable predictions for the bond properties between GFRP bars and CAC.