The evocatively named "Black Amazon of Mars" is a short story by Leigh Brackett, first published in the March 1951 issue of Planet Stories and later revised and expanded in 1964 under the title People of the Talisman (under which title it's included in Paizo's The Secret of Sinharat trade paperback). It's a tale of Mercurian mercenary fighting man Eric John Stark, who's the protagonist of many of Brackett's science fiction tales published during the 1940s and 50s. Originally set within a version of our solar system based on the science of the 30s and 40s, Stark's adventures eventually moved to another solar system in order to accommodate a shift in popular taste toward more "realistic" SF stories that were in tune with later developments in planetary science.
Part of Brackett's earlier cycle, "Black Amazon of Mars" is set on the fourth planet of our solar system, as one might expect from its title. In it, Stark is on Mars, traveling in the company of a thief named Camar. Camar is mortally wounded and he asks Stark to take him to his home city before he dies of his injury. The thief also confesses that he has stolen a holy talisman believed to keep the city safe and he begs Stark to see it returned, no matter what happens. A man who keeps his promises, Stark then proceeds on an adventure that takes him to several different locales near the Martian north pole, encountering numerous allies and foes, including the character after whom the short story is named. Along the way, he must deal with not only ordinary obstacles but also mysterious visions of a place to which he's never been and that may hold the key to his quest.
Like all of Brackett's stories of Stark, "Black Amazon of Mars" could be called science fantasy, but that's probably unfair. Certainly its vision of Mars is more in line with that of Burroughs and other early writers than with what we now know about the Red Planet. At the time the Stark stories began, though, it was still possible to imagine an inhabited Mars, even if it was increasingly implausible. In any case, Brackett didn't intend her stories to be read as fantasies and, if one can leave aside the outdated science, they don't read as such. Furthermore, Brackett's solar system is a cosmopolitan place, filled with inhabited worlds to which travelers journey by regular rocket flights. Stark may be an unusual man because of his personality and outlook but he's not unique in being a space traveler. He's no John Carter or Esau Cairn; in short, he's not a sword-and-planet hero. Rather, he's closer to an interplanetary revolutionary, fighting against colonialist oppression in a solar system that treats commerce and competition as the highest virtues -- a hero very much unlike other SF protagonists of his day.
"Black Amazon of Mars" is well written and fast paced. It may not appeal to all tastes, particularly those used to more modern takes on science fiction. Nevertheless, it's a terrific example of SF from its time, filled with memorable characters and occasional insights that set it apart from rank and file space opera. Gary Gygax noted Leigh Brackett as an influence on Dungeons & Dragons without specifying any particular stories he considered most significant. I find it unlikely that he was not referencing the stories of John Eric Stark, which are, above all, superb adventure takes. That they have additional depth beyond that is merely icing on a very sweet cake.