In search for new magnetic materials, we make computer prediction of structural, electronic and magnetic properties of yet-to-be synthesized Rh-based double perovskite compounds, Sr(Ca)2BRhO6 (B=Cr, Mn, Fe). We use combination of evolutionary algorithm, density functional theory, and statistical–mechanical tool for this purpose. We find that the unusual valence of Rh5+ may be stabilized in these compounds through formation of oxygen ligand hole. Interestingly, while the Cr–Rh and Mn–Rh compounds are predicted to be ferromagnetic half-metals, the Fe–Rh compounds are found to be rare examples of antiferromagnetic and metallic transition-metal oxide with three-dimensional electronic structure. The computed magnetic transition temperatures of the predicted compounds, obtained from finite temperature Monte Carlo study of the first principles-derived model Hamiltonian, are found to be reasonably high. The prediction of favorable growth condition of the compounds, reported in our study, obtained through extensive thermodynamic analysis should be useful for future synthesize of this interesting class of materials with intriguing properties. A computational study predicts that new magnetic materials could be made from rhodium-based double perovskites. Magnetic materials are exploited in many technologies and applications but compounds with technologically-useful magnetic properties are surprisingly rare. A team of researchers from India, led by Tanusri Saha-Dasgupta from the S. N. Bose National Centre for Basic Sciences and the Indian Association for the Cultivation of Science, now use computational methods to predict that that rhodium-based double perovskites could host a range of interesting magnetic properties. Combining several computational techniques, including a genetic evolutionary algorithm, the authors predict that some of these perovskites could be half-metallic ferromagnets, which could find applications in spintronics, whilst others may be metallic antiferromagnets. With thousands of double perovskites available, this could be a rich class of materials for magnetism.