Legendary Wings takes place 20,000 years in the future in a Greek mythos-themed world. The player controls a soldier wearing mechanical wings who flies across the landscape while shooting various flying and stationary machines with a weapon that improves with power-ups. During each level, the player enters a cave; once inside the cave, the player walks along various platforms, shooting fire-breathing monsters before reaching a boss. Upon defeating the boss, the player returns to flight to complete the level. The game features 5 separate levels, which loop upon completion.