Cyamelurate anions obtained from the hydrolysis of polymeric graphitic carbon nitride were used for the preparation of a water-stable and crystalline coordination polymer based on nickel(II)–cyamelurate. The polymer was prepared and applied as a catalyst for the reduction of 4-nitrophenol to 4-aminophenol in the presence of borohydride under ambient conditions. The catalyst was prepared by a simple and environmentally friendly method in an aqueous medium, and it was completely characterized by a variety of techniques, including FTIR, UV–Vis, XRD, TGA, TEM, and STEM. The obtained catalyst was able to catalyze the reaction of 4-nitrophenol to 4-aminophenol with a good kinetic constant. In addition, the catalyst proved to be significantly robust, maintaining a conversion rate greater than 80% after five minutes of reaction for eight consecutive catalytic cycles. In addition, the catalytic activity of the coordination polymer was much higher than that observed for a homogeneous catalyst based on aqueous Ni2+ ions, suggesting the importance of the structure of the coordination sphere formed by the cyamelurate anions. The results presented here can contribute to the application of other coordination polymers anchored with cyamelurate-like ligands and derivatives, as well as to new catalyst designs based on this coordination site formed by oxygen and nitrogen donor atoms.