The interplay of structural and electronic phases in iron-based superconductors is a central theme in the search for the superconducting pairing mechanism. While electronic nematicity, defined as the breaking of four-fold symmetry triggered by electronic degrees of freedom, is competing with superconductivity, the effect of purely structural orthorhombic order is unexplored. Here, using x-ray diffraction (XRD), we reveal a new structural orthorhombic phase with an exceptionally high onset temperature ($T_mathrm{ort} sim 250$ K), which coexists with superconductivity ($T_mathrm{c} = 25$ K), in an electron-doped iron-pnictide superconductor far from the underdoped region. Furthermore, our angle-resolved photoemission spectroscopy (ARPES) measurements demonstrate the absence of electronic nematic order as the driving mechanism, in contrast to other underdoped iron pnictides where nematicity is commonly found. Our results establish a new, high temperature phase in the phase diagram of iron-pnictide superconductors and impose strong constraints for the modeling of their superconducting pairing mechanism.