But it is. He says that given a list of primes P1, P2, ..., PN, construct (P1 * P2 * ... * PN) + 1, which is a new prime not on the list, so given any finite list we can always construct more primes.
For example, (2 * 3 * 5 * 7 * 11 * 13) + 1 is 30031, which is 59 * 509
(Apparently I misremembered the details of Euclid's proof. See the comments below.)
I thought that it started with (P1, P2, P3, ..., PN) being a list of all the primes from 2 up to PN. Since (P1 * P2 * ... * PN) + 1 either is prime or has a prime factor not in the list, that prime factor must be greater than PN.
Apparently (according to Wikipedia's summary) Euclid started with an arbitrary list of primes, and showed that for any such list there is a prime not in the list.
Either method works to show that there are infinitely many primes.
For example: 3*5 + 1 = 16, not prime.
Euclid's argument is that the product of some primes plus one is either prime or not; if it's prime, then it's an example of a prime that is not in the list. If it is not prime, then Euclid argues that the number's prime factors are not in the list.
To directly use Euclid's result to find a new prime number, we have to multiply some existing numbers together, add 1, and then factor that number. If it doesn't factor, then it is a new prime; otherwise its factors are new primes.
That seems constructive; all of the steps amount to a terminating algorithm that will give us at least one new prime.