Lou Costello and John Wayne debuted in the same movie!

Cafe Society
1

At least that’s the case if I accept the IMDB entries for Bardelys the Magnificdent:

From the IMDB we also learn that Costello played an extra in two films with Joan Crawford, and in one Laurel and Hardy epic, The Battle of the Century:

All before teaming up with Bud Abbott.

2

Although the IMDB entry for John Wayne credits him with one flick earlier in the year:

http://www.imdb.com/name/nm0000078/

3

This site confirms that Wayne’s in it, but can’t confirm the presence of Costello.

Moreover, all that’s definately know to survive of it is a five-minute trailer, so we can’t view it again to see if he’s really in it.

(The note at the bottom of my link appears to be in error, as I haven’t found a reference to it anywhere else.)

4

I note that the cast list reads:

The IMDB also credits Costello as stunt double for Dolores Del Rio (!!) in The Trail of '98:

http://www.imdb.com/title/tt0019489/fullcredits