The original All-Star Western began with #58 (May 1951), having taken over the number of its predecessor title, All Star Comics — a superhero omnibus that years before had introduced the enduring team the Justice Society of America.

The first issue contained the features "The Trigger Twins", created by writer Robert Kanigher and penciler Carmine Infantino and running through #116; "Don Caballero", drawn by Gil Kane, and "Roving Ranger", penciled by Alex Toth, the writer-creator uncredited; and "Strong Bow", created by writer David Wood and artist Frank Giacoia.

The series was revived in the following decade, and ran 11 bimonthly issues (Sept. 1970 – May 1972) before changing its title and, slightly its format to become Weird Western Tales.

Issue #10 (February–March 1972) introduced the enduring and popular character Jonah Hex, created by writer John Albano and artist Tony DeZuniga.

The series was revived as part of the line-wide The New 52 relaunch in September 2011, written by Justin Gray and Jimmy Palmiotti with art by Moritat.