Studio execs were sending really confusing messages for the entire production. On one hand, nobody from the studio liked the idea of making a horror movie (even if the book is a historical fiction mixed with horror), while in the end, when the movie was ready, they wanted to make it Darker and Edgier, so what was shot as a PG-13 movie had suddenly a bunch of gorn scenes added to it to get it R-rated. McTiernan absolutely hated the whole mess, as if the movie was R-rated from the start, he would have shot it in completely different way.
When initial marketing for the movie already started, the title was suddenly changed from Eaters of the Dead to 13th Warrior and the R-rated decision was made in the middle of it, with the production already wrapping. And despite the decision to get the film R-rated, the marketing was tasked with exact reverse - to spin instead Lighter and Softer trailer, because the original one was deemed "too scary".
The studio was also against the fact Ahmad was Arab or using any sort of Muslim references, trying to remove them entirely from the story, or at least tone them down considerably. Standing against such changes was probably the only thing Crichton and McTiernan were both united.
The entire character of the Wendol leader and his sudden importance was thrown in on studio demand, because execs wanted to have a duel involving Buliwyf in the end of the movie. It shows.
If actors are to be believed, the version by McTiernan was rife with Show, Don't Tell moments, but in the process it extended numerous scenes, ending with a final runtime of well over two hours. The studio panicked and trimmed almost all of it out, making numerous scenes much more literal or replaced with brief expositions (like the visit to the mad seer). Entire sequences were removed fully, leading to a few minor plot holes.
The execs finally decided to shoot two endings, one by McTiernan, other under Crichton. Thing is - it was already decided before even the shooting restarted that Crichton's version will be used as the final cut, keeping crew and actors in the blind about it, but giving them double work to do. This obviously bloated the budget further, encouraging the studio to dump the movie as fast as possible.
Screwed by the Network: After three years of work, constant in-fights, forcing countless changes and gutting the third part of the movie, the studio decided to just drop it into cinemas, without premiere, marketing and just get rid of it, before it would cost another million or two to maintain the production. It singlehandly shot any chances the film ever had dead in the water. Everyone involved in the production points the execs' indifference toward the movie as the main reason it underperformed horribly.
Star-Derailing Role: A temporary example. Omar Sharif had such a bad experience on the set of the film and was so disappointed by the final cut that he briefly retired from acting.
Star-Making Role: One of the best things about this film is that it helped jumpstart Vladimir Kulich's career. What makes it even more amazing is the fact the film was a complete bomb and he still made it big thanks to it.
Troubled Production: The film was reshot at least twice before test screenings. Two scores were written. Countless Executive Meddlings halted production a few times, forcing the crew and actors to start from scratch. Then there was another reshooting after unsatisfying results from test screenings, one year after the production was already wrapped. There was apparently poor teamwork between crew and actors (Omar Sharif said a lot of harsh words about McTiernan's skills as director) and open conflict between execs, McTiernan and Crichton about the screenplay. Dennis Storhøi almost drowned. A horse was killed during the production, slowing it even further. It's a wonder the film didn't end up in Development Hell.
Vindicated by Cable: Seems to be heading in this direction. The film's production issues may have crippled it as a blockbuster, but sandwiched between b-movies and Mockbusters as part of an afternoon movie marathon, it's a pleasant surprise.
The film was heavily cut after poor reactions to test screenings and this shows up badly in the theatrical version — it's very clear entire sections of the film have been left on the cutting room floor in an attempt to make the film more appealing to a popular audience. In a pre-Harry Potter and The Lord of the Rings era, which proved audiences were perfectly happy to sit through long fantasy-themed films, it's obvious the studio panicked at the poor test screening results and butchered the film. Ironically the cut down version received poor reviews and performed badly at the box office whereas who's to say how the originally envisaged version might have been received?
The score written by Graeme Revell was replaced with one written by Jerry Goldsmith. There are at least a few fan-made montages using Revell's soundtrack, but since each track got only a number, it's a wild guess where to fit which.
The earlier versions were apparently much closer to the book. Ironically, it was Crichton out of all people who was responsible for final changes in the movie, distancing it significantly from the novel.
Rather than making an epic adventure movie, McTiernan was trying to make a tense thriller, a la his debut, Predator. The first trailer, made when the movie was still under the "Eaters of the Dead" working title and before heavy recutting, literally screams its nature as a horror-thriller cross, further helped by the (later dropped) score by Graeme Revell, with its characteristic beat taken from his famous Dead Calm OST. Just compare it with the final trailer. No, this is not a mock trailer - that's how bad the marketing of the movie was.
Vladimir Kulich wasn't the first choice for the role. Both the studio and Crichton wanted Stellan Skarsgård instead to play Buliwyf.