We use scanning tunneling microscopy (STM) to investigate the spatial arrangement of carbon monoxide (CO) and hydrogen (H) coadsorbed on a model catalyst surface, Ru(0001). We find that at cryogenic temperatures, CO forms small triangular islands of up to 21 molecules with hydrogen segregated outside of the islands. Furthermore, whereas for small island sizes (3-6 CO molecules) the molecules adsorb at hcp sites, a registry shift toward top sites occurs for larger islands (10-21 CO molecules). To characterize the CO structures better and to help interpret the data, we carried out density functional theory (DFT) calculations of the structure and simulations of the STM images, which reveal a delicate interplay between the repulsions of the different species.