The structures of ruthenium cluster anions have been investigated using a combination of trapped ion electron diffraction and density functional theory computations in the size range from eight to twenty atoms. In this size range, three different structural motifs are found: Ru8(-)-Ru12(-) have simple cubic structures, Ru13(-)-Ru16(-) form double layered hexagonal structures, and larger clusters form close packed motifs. For Ru17(-), we find hexagonal close packed stacking, whereas octahedral structures occur for Ru18(-)-Ru20(-). Our calculations also predict simple cubic structures for the smaller clusters Ru4(-)-Ru7(-), which were not accessible to electron diffraction measurements.