Let $\mathcal H_n\subset \mathbb C^{n\times n}$ be the class of $n\times n$ Hessenberg matrices A which are rank‐one modifications of a unitary matrix, that is, $A=H +\B u\B w^H$, where H is unitary and $\mathbf{u}, \mathbf{w}\in \mathbb C^n$. The class $\mathcal H_n$ includes three well‐known subclasses: unitary Hessenberg matrices, companion (Frobenius) matrices, and fellow matrices. The paper presents some novel fast adaptations of the shifted QR algorithm for computing the eigenvalues of a matrix $A\in \mathcal H_n$ where each step can be performed with $O(n)$ flops and $O(n)$ memory space. Numerical experiments confirm the effectiveness and the robustness of these methods.