Computational design of more efficient rare earth/transition metal (RE-TM) permanent magnets requires accurately calculating the magnetocrystalline anisotropy (MCA) at finite temperature, since this property places an upper bound on the coercivity. Here, we present a first-principles methodology to calculate the MCA of RE-TM magnets which fully accounts for the effects of temperature on the underlying electrons. The itinerant electron TM magnetism is described within the disordered local moment picture, and the localized RE-4f magnetism is described within crystal field theory. We use our model, which is free of adjustable parameters, to calculate the MCA of the RCo$_5$ (R=Y, La-Gd) magnet family for temperatures 0--600 K. We correctly find a huge uniaxial anisotropy for SmCo$_5$ (21.3 MJm$^{-3}$ at 300 K) and two finite temperature spin reorientation transitions for NdCo$_5$. The calculations also demonstrate dramatic valency effects in CeCo$_5$ and PrCo$_5$. Our calculations provide quantitative, first-principles insight into several decades of RE-TM experimental studies.