The coupling of ordered electronic phases with lattice, spin, and orbital degrees of freedom are of central interest in strongly correlated systems. Their interplay has been intensively studied from femtosecond to picosecond time scales, while their dynamics beyond nanoseconds are usually assumed to follow lattice cooling. Here, we report an unusual slowing down of the recovery of an electronic phase across a first-order phase transition. Following optical excitation, the recovery time of both transient optical reflectivity and X-ray diffraction intensity from the charge-ordered superstructure in a La1/3Sr2/3FeO3 thin film increases by orders of magnitude as the sample temperature approaches the phase transition temperature. In this regime, the recovery time becomes much longer than the lattice cooling time. The combined experimental and theoretical investigation shows that the slowing down of electronic recovery corresponds to the pseudo-critical dynamics that originates from magnetic interactions close to a weakly first-order phase transition.