Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Computing a generating set of invariants (sometimes called the computational problem of &quot;Noether's Normalization Lemma&quot;) for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You can also talk about $SL_m$, but it's just a little cleaner to state the results when $m=3$.)
Went from non-constructive proof of finiteness, to computable, to EXPSPACE, to nearly-polynomial, over the course of over a century.
As discussed in GCT V: Hilbert originally proved that the invariant ring $\mathbb{C}[V]^{SL_3}$ was finitely generated non-constructively. After Gordan's criticism, Hilbert [1893] gave an algorithm, showing (in modern language) that a finite generating set can be computed in finitely many steps (so, the problem became computable). Degree bounds proved nearly a century later by Popov and then Derksen combined with Gröbner basis puts it into $\mathsf{EXPSPACE}$. In GCT V, Mulmuley put this problem into time $n^{O(\log \log n)}$.