Legendary Wings está ambientado en un futuro lejano, donde una supercomputadora extraterrestre llamada "Dark", que ha estado ayudando a la civilización humana a alcanzar un nuevo estado de la iluminación desde la antigüedad, de repente se ha rebelado contra la humanidad.
El juego consta de cinco áreas con dos estilos de juego diferentes: el primer segmento en cada etapa es un segmento con scroll vertical y perspectiva cenital, en el reproductor el jugador vuela a través del cielo, disparando a enemigos en el aire con su arma mientras lanza bombas a los enemigos en tierra, con el fin de llegar al palacio al final del segmento.
El jugador puede mejorar su pistola al destruir ciertos enemigos o cápsulas de armas, recogiendo el ítem "P" que liberan.
El jugador puede potenciar su personaje hasta cinco niveles: el primero aumentará la velocidad del jugador, el segundo cambiará su arma a un tirador doble y aumentará aún más su velocidad; el tercero permite continuos ataques de tierra, el cuarto mejora la pistola del jugador para que dispare en tres direcciones, y el quinto y último mejora el arma a la pistola "Psycho Flame" (psico-llama), que puede destruir la mayoría de los enemigos con un solo disparo.
Como en el arcade, el jugador puede incrementar su potencia de fuego recogiendo los iconos "P" ocultos en ciertos contenedores.