Highly excited molecular species are at play in the chemistry of interstellar media and are involved in the creation of radiation damage in a biological tissue. Recently developed ultrashort extreme ultraviolet light sources offer the high excitation energies and ultrafast time-resolution required for probing the dynamics of highly excited molecular states on femtosecond (fs) (1 fs=10(-15) s) and even attosecond (as) (1 as=10(-18) s) timescales. Here we show that polycyclic aromatic hydrocarbons (PAHs) undergo ultrafast relaxation on a few tens of femtoseconds timescales, involving an interplay between the electronic and vibrational degrees of freedom. Our work reveals a general property of excited radical PAHs that can help to elucidate the assignment of diffuse interstellar absorption bands in astrochemistry, and provides a benchmark for the manner in which coupled electronic and nuclear dynamics determines reaction pathways in large molecules following extreme ultraviolet excitation.