Bulk rutile RuO$_2$ has long been considered a Pauli paramagnet. Here we report that RuO$_2$ exhibits a hitherto undetected lattice distortion below approximately 900 K. The distortion is accompanied by antiferromagnetic order up to at least 300 K with a small room temperature magnetic moment of approximately 0.05 $mu_B$ as evidenced by polarized neutron diffraction. Density functional theory plus $U$ (DFT+$U$) calculations indicate that antiferromagnetism is favored even for small values of the Hubbard $U$ of the order of 1 eV. The antiferromagnetism may be traced to a Fermi surface instability, lifting the band degeneracy imposed by the rutile crystal field. The combination of high Neel temperature and small itinerant moments make RuO$_2$ unique among ruthenate compounds and among oxide materials in general.