Ab initio pseudopotential calculations of the atomic structures and magnetic behavior of Rhn (n≤15) clusters using the generalized gradient approximation for the exchange-correlation energy, reveal new lowest energy structures that are noncompact and have no atom at the center upto n=13, leading to a nonicosahedral growth. An eight-atom cluster has cubic structure and is magic. Some clusters beyond 13 atoms also do not have close packed structures due to some covalent character in the bonding. The calculated magnetic moments are generally lower and in better agreement with experiments than obtained before. Further studies on Ru13 and Pd13 clusters show that the lowest energy isomers of these clusters are also nonicosahedral. These findings of the novel behavior of technologically important transition metal clusters provide new ground for a better understanding and design of new catalysts.