The structure of CO adsorbates on the Rh(110) surface is studied at full coverage using first-principles techniques. The relative energies of different adsorbate geometries are determined by means of accurate structure optimizations. In agreement with experiments, we find that a p2mg(2x1) 2CO structure is the most stable. The CO molecules sit on the short-bridge site (carbon below) with the molecular axis slightly tilted off the surface normal, along the (001) direction. Configurations corresponding to different distributions of tilt angles are mapped onto an anisotropic 2D Ising model whose parameters are extracted from our ab-initio calculations. We find that an order-disorder phase-transition occurs at a temperature T_c=350 K. Comment: 4 pages, latex file, 2 figures included