The institution originally opened in the Varied Industries Building at Fair Park, Dallas, in September 1963. It was founded by W. Thomas Bolton, John A. Prather, and J. C. Brown. The museum's exhibits included scenes of western gunfights and many historical figures of the southwest such as Cynthia Ann Parker and Antonio López de Santa Anna. A number of other figures included Bonnie Parker and Clyde Barrow, John F. Kennedy, and Elvis Presley. The museum also included a collection of firearms once owned by the outlaws and heroes of the Southwest. By 1982 the museum had moved to its Grand Prairie location and was operated there until a fire destroyed it in October 1988.
In January 1989 the owners of the museum, Classic Attractions, Incorporated, announced the construction of a new wax museum on the site of the old museum. They renamed it the Palace of Wax. The new structure also included a Ripley's Believe It or Not! museum. Both museums are housed in a 41,000-square-foot building fashioned after an Arabian palace. The new wax museum contains approximately 100 wax figures crafted by the museum's sculptor, Peter Carsillo.