That the cationic polyelectrolyte poly(allylamine hydrochloride) (PAH) exerts a significant influence on CaCO₃ precipitation challenges the idea that only anionic additives have this effect. Here, we show that in common with anionic polyelectrolytes such as poly(aspartic acid), PAH supports the growth of calcite thin films and abundant nanofibers. While investigating the formation of these structures, we also perform the first detailed structural analysis of the nanofibers by transmission electron microscopy (TEM) and selected area electron diffraction. The nanofibers are shown to be principally single crystal, with isolated domains of polycrystallinity, and the single crystal structure is even preserved in regions where the nanofibers dramatically change direction. The formation mechanism of the fibers, which are often hundreds of micrometers long, has been the subject of intense speculation. Our results suggest that they form by aggregation of amorphous particles, which are incorporated into the fibers uniquely at their tips, before crystallizing. Extrusion of polymer during crystallization may inhibit particle addition at the fiber walls and result in local variations in the fiber nanostructure. Finally, we investigate the influence of Mg²+ on CaCO₃ precipitation in the presence of PAH, which gives thinner and smoother films, together with fibers with more polycrystalline, granular structures.