Capcom's 1991 arcade game Street Fighter II was turning point for fighting games and escalated the genre to greater popularity than ever before. As impressive as it was, it tends to overshadow its predecessors. Fighting games were well established by this time, and had seen plenty of innovations before the birth of Street Fighter.
At what point the genre was born is debatable because of the conventions of a genre crystallize over time, but games that involved two characters duelling date back as far as 1976 with arcade releases like Sega's boxing game Heavyweight Champ and Project Support Engineering's jousting game Knights in Armor. Though related, boxing has become its own sub-genre of sports gaming so I won't bother including it for the rest of article.
Another early duelling game was Warrior, an arcade release by Vectorbeam in 1979. It involved two swordfighters, and was played from an overhead perspective. The characters were drawn in vectors while an overlay provided the dark background with spiralling staircases.
Fighting games tend to be more associated with martial arts than medieval jousting and sword slashing, though. The first martial arts-themed fighting games started appearing around 1982. Ultravision's Atari 2600 game, simply titled Karate, was a crude attempt on the theme(even by the standards of the time).
Atari was developing a 5200 game around this time called Black Belt which had one-on-one fighting while travelling to various rooms but it never made it past the prototype stage. Ebenel's 1983 DOS game Bushido: The Way of the Warrior similarly had a character that moved to different rooms to fight opponents.
The following year had one of the most important games in the history of the genre, the arcade release Karate Champ, which was developed by Technos and distributed by Data East. Not only was it graphically more impressive than any other fighting game at the time, it had bonus rounds, voices, and was more complex as it gave you higher points for landing better blows. Being the first mainstream hit in the genre made it an influence on other developers.
Also from 1984 was the Apple II game Karateka by Prince of Persia creator Jordan Mechner. While the game does have your character run to new areas (a design trait more associated with platformers and beat 'em ups), the action is still focused on one-one-one fighting. Karateka introduced in-game cinemas to the genre. It was ported to several other formats.
Konami's 1985 arcade game Yie Ar Kung Fu introduced a wide variety of opponents including female characters, and had the beginnings of combo-based gameplay. The MSX and Famicom versions were not ports of the arcade game while the Western computer versions released by Imagine were.
Konami released another arcade fighting game that year but it didn't receive the same level of recognition. Galactic Warriors took the genre into sci-fi territory. The gameplay was more sluggish than Yie Ar Kung Fu but the graphics were striking, and it let you choose between three different robots which could toggle between different types of moves (melee, weapon, and shield, for example).