Ultra-small chromium oxide nanoclusters produced by laser vaporization in a fast flow tube reactor are ligand-coated by gas-phase reactions with acetonitrile vapor and then captured in a cold trap and transferred to solution. The resulting clusters are characterized with mass spectrometry, UV-visible absorption and emission spectroscopy, infrared spectroscopy, and surface-enhanced Raman spectroscopy. According to mass spectrometry, clusters of the form CrxOy (MeCN)(z) are produced in the size range of x <= 10 and y < 25. The ligand-coated clusters in solution exhibit a limited number of prominent sizes, with the same preferences for specific stoichiometries seen in earlier gas-phase studies of ligand-free clusters. Computational studies provide structures and predicted spectra for these systems. The intrinsic stability of these clusters is confirmed by their production under different laser ablation conditions and by their significant shelf lives (several months) without aggregation or decomposition. UV-visible spectra indicate that these clusters contain highly oxidized chromium. Theory and previous experiments indicate that compact cages are favored for ligand-free clusters. However, infrared and Raman spectra suggest that ring and chainlike structures become prominent for ligand-coated clusters. Consistent with these observations, theory also indicates that these more open structures are energetically favored for ligated clusters. Apparently, ligand binding induces a structural transformation of the compact oxide core clusters, producing more extended ring and chain structures.