We discover a robust coexistence of superconductivity and ferromagnetism in an iron arsenide RbEuFe$_4$As$_4$. The new material crystallizes in an intergrowth structure of RbFe$_2$As$_2$ and EuFe$_2$As$_2$, such that the Eu sublattice turns out to be primitive instead of being body-centered in EuFe$_2$As$_2$. The FeAs layers, featured by asymmetric As coordinations, are hole doped due to charge homogenization. Our combined measurements of electrical transport, magnetization and heat capacity unambiguously and consistently indicate bulk superconductivity at 36.5 K in the FeAs layers and ferromagnetism at 15 K in the Eu sublattice. Interestingly, the Eu-spin ferromagnetic ordering belongs to a rare third-order transition, according to the Ehrenfest classification of phase transition. We also identify an additional anomaly at $sim$ 5 K, which is possibly associated with the interplay between superconductivity and ferromagnetism.