Why was the winner of the AES competition not a Feistel cipher? The winner of the AES competition has a structure that does not qualify as a Feistel cipher, as explained in answers to this recent question.

However, most many of the AES candidates, and all 3 out of 4 some other finalists (Twofish, MARS) are Feistel ciphers, if we define that as a cipher transforming a block of data using a number of rounds which each can be expressed as:


split all the bits of the block $B_j$ into two disjoint portions $L_j$ and $R_j$ (typically of equal size);
compute some (typically round-dependent) function of $R_j$ and key with output $F_j$ of same width as $L_j$;
compute  $L_j'=L_j\oplus F_j$ where $\oplus$ is binary addition with removal of some carry bits (e.g. exclusive-OR, where all carry bits are removed);
recombine bits of $L_j'$ and the unmodified $R_j$ into a new block $B_{j+1}$.


Note: Serpent and RC6 can not be put in this framework (thanks to @Reid and @J.D. for pointing that). Neither can Rijndael/AES.

At the time of the AES competition, Feistel ciphers already enjoyed a well understood theory. In particular DES was among them, and essentially unbroken in practice except for its small key and block size. It would seem that proposing anything else than a Feistel cipher would be an uphill battle.

Yet, Rijndael won the AES competion, and does not fall under the above definition. Did a desirable characteristic of Rijndael made it preferred to the other candidates despite the apparent drawback of using a relatively untested structure? And if that characteristic could not be matched by a Feistel cipher, why?
DES actually demonstrated that a Feistel structure was not a guarantee against attacks. In "academic" terms, DES is broken by both differential and linear cryptanalysis, because they require, respectively, $2^{47}$ chosen plaintexts and $2^{43}$ known plaintexts, whereas the DES key is (effectively) 56 bits. Of course, for practical attacks, we would brute force the key: computing the function $2^k$ times is vastly easier than obtaining $2^k$ known plaintext/ciphertext pairs (or, even worse, chosen plaintext/ciphertext pairs). But in the usual "academic" evaluation of security, both linear and differential cryptanalysis count as breaks.

Luby and Rackoff have demonstrated in 1988 that given "perfect" round functions, a four-round Feistel structure is secure. However, this proof has two practical issues:


It is relative to the output size of the round function, i.e. 32 bits for a 64-bit block cipher. For 128-bit security, blocks have to be 256-bit wide for the proof to actually apply; but the AES call for candidates requested 256-bit security with 128-bit blocks, not the other way round.
DES has amply demonstrated that concrete round functions cannot be assumed to be perfect.


So while the security provided by a Feistel structure was already quite well understood at that time (around 1997, when AES candidates were being designed), it was also quite known to be "suboptimal" in the following sense: to get the most out of the existing security proofs, you had to go to impractical block sizes or number of rounds. Indeed, many researchers were dissatisfied with the Feistel structure, and eager to explore new structures. The AES competition was at the right time to become a test bed for such novel designs, and the accumulated research has shown substitution-permutation networks (as used by Rijndael) to be valid competitors to Feistel structures.