About 25 years ago more or less, a friend and I remember seeing this 3D action adventure platformer PC game, with a dark fantasy theme. There were three main characters: a warrior that looked really bulky and slightly monstruous, he had a half-mask of sorts that covered his mouth and nose, I remember he was bald and wielded a huge axe. The other character was a wizard/sorcerer type character, that was completely covered in bandages, he kinda looked like a mummy with a dark hood. I don't remember the appearance of the third main character clearly, but I'm sure it was a female character, she kinda resembled a dark elf.

The story on the back of the box sounded pretty edgy, with some sort of evil army or empire that was ravaging the land, and each of these three characters had a personal vendetta to oppose this terrible army.

Back then, we just saw it once at the mall on our way to meet up with some guys, and we foolishly thought it would still be there when we came back, but to our unpleasant surprise, the game was gone when we returned! We didn't pay attention to it, thinking that it would be back on sale eventually; and it never appeared on the shelves again. I am still curious as to what that game was. Does anybody have a clue as to what game it could be, based on the extremely vague info that I provided?

Could it have been Severance: Blade of Darkness? It was here on GOG for a while but had to be removed again.

But it doesn't feature a wizard ... only these: "Tukaram, a barbarian; Naglfar, a dwarf; Sargon, a knight; and Zoe, an amazon"

Or Enclave?

Those are the better known ones that I can think of, but of course it could have been something more obscure. 1995 seems a bit early for this type of 3D game on PC though, about 20 years ago seems more likely. (Although there's also Ecstatica from 1994, and Die by the Sword and Deathtrap Dungeon from 1998, but I'm not sure whether they would fit the description; I don't think they have wizards as playable characters either ...)

I think I might have found it: Was it Dark Vengeance (1998)?

Great, now I want all of these on GOG. ;)

Dark Vengeance
Nightmare Creatures (1997)
Archangel (2002)

It seems the sequel was a console exclusive though?

Ah, yes, that is correct; I wish we could get a PC port.