Un generador de agujeros negros supone una amenaza directa para la humanidad al permitir el acceso de las tropas Stroggs a la Tierra. Los líderes mundiales planean la Operación Alien Overlord, calcada de la invasión de Normandía de 1944, que implica el desembarco de un gran número de tropas en Stroggos, la capital de los Stroggs, donde se encuentra el famoso cañón Big Gun para evitar un desembarco a mayor escala (al iniciarse el juego, aparece en pantalla una orden de misión muy similar a la que se distribuyó a los soldados estadounidenses en 1944, salvo que termina con la frase: "¡Así que salid y patead culos soldados!").
Grandes naves de transporte atacan Stroggos a través de lo que parece ser un vórtice gigante, descargando numerosas pequeñas lanzaderas personales. El jugador se encuentra a bordo de una de estas lanzaderas, y en la cinemática introductoria, sobrevuela la ciudad, describe un gran círculo alrededor de la monstruosa Big Gun, antes de estrellarse en un suburbio remoto, pero aún sólidamente vigilado.