To the best of my knowledge, the two major breakthroughs in regarding negative results in computation/recursion theory came in 1936 by Church and Turing. They both prove that some variant of the Halting problem was undecidable.
However, a very simple proof of the statement "There is an undecidable problem" already existed at that time, namely the fact that there are simply too many problems and too few algorithms.
Assuming that any algorithm has a finite description, and that they take natural numbers as input, we are trying to make a bijection between the natural numbers $\mathbb{N}$ and its powerset $2^{\mathbb{N}}$.
Adopting Cantor's diagonal argument to Machines, we can observe that if $\mathcal{M} = \{M_i \mid i \in \mathbb{N}\}$ is the set of machines, and for every machine $M \in \mathcal{M}$, that $M(n)$ is either yes (halts) or no (does not halt), for $n \in \mathbb{N}$.
Then we can construct the set $$U = \{i \in \mathbb{N} \mid M_i(i) \text{ is no} \}$$ like Cantor would, and pick the $i$ s.t. the domain of $M_i$ is $U$, and ask whether $i \in U$, in both cases reaching a contradiction.
Question: Why wasn't this discovered between 1875/90 and 1935? (Or was it?)