Quantum magnonics is a new and active research field, leveraging the strong collective coupling between microwaves and magnetically ordered spin systems. To date work in quantum magnonics has focused on transition metals and almost entirely on ferromagnetic resonances in yttrium iron garnet. Antiferromagnetic systems have gained interest as they produce no stray field, and are therefore robust to magnetic perturbations with narrow, shape independent resonant linewidths. Rare-earth ion spins are also of particular interest as they can exhibit narrow optical and microwave transitions and have large magnetic dipole moments. Here we show experimental evidence of ultrastrong-coupling between a microwave cavity and collective antiferromagnetic resonances (magnons) in a fully concentrated rare-earth crystal. Using a loop-gap microwave resonator a coupling strength of 1.75 GHz is obtained between the cavity and the antiferromagnetic resonances in a GdVO4 sample. Furthermore we measure the linewidth of the antiferromagnetic magnon to be 35 MHz, proving that narrow magnon linewidths can be achieved in rare-earth crystals. The combination of the unique optical and spin properties of the rare earths and collective antiferromagnetic order paves the way for quantum magnonic applications.