The combination of advanced solid-state NMR spectroscopy, powder X-ray diffraction (PXRD), structure refinement, and quantum chemical calculations was used to determine the three-dimensional molecular structures of self-assembled, one-dimensional (1D) metal coordination polymers. The methodology is based on partial indexing of PXRD patterns followed by modeling using NMR constraints and, finally, Rietveld refinement and density functional theory (DFT) structure optimization. The protocol was first demonstrated on scandium acetate, a 1D coordination polymer with a known structure. The protocol was then applied to determine the crystal structures of nanocrystalline aluminum and gallium acetate hydroxide coordination polymers of unknown structures that were obtained by the etching of metallic nanoparticles in acidic solution. The PXRD and NMR-derived structures were validated by comparing the experimental and simulated PXRD patterns. Plane-wave DFT calculations confirm that the structures are energetically stable and that DFT-predicted NMR parameters are in reasonable agreement with the experimentally observed ones. The obtained molecular structures are in agreement with data from other characterization methods. The structure determination protocol demonstrated here should be applicable to analogous coordination polymers or porous framework materials.