I have managed to trace back Skolem's normal form to Skolem's "Logico-combinatorial investigations in the satisfiability or provability of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem".
What is the origin of prenex normal form?