The producers briefly considered setting the series on Bajor itself, within a planet-based facility, with heavy use of location filming for the exteriors of the base. Though hardly a huge change to the format of the eventual series, it would have opened up storytelling possibilities, with some Bajorans suspecting that they'd simply traded one set of occupiers for another (an idea which nevertheless made it into the series).
An early idea for the Deep Space 9 space station had it be thousands of years old and gave it a chaotic, asymmetrical design as a result of various alien races modifying it over the millennia.
The role of Major Kira was initially intended to be Next Generation recurrer Ro Laren, which was the entire reason for setting the show near Bajor. Michelle Forbes didn't want to commit to a full television series, so the new character of Major Kira was created. Ro would end up serving as the station's chief of security in the relaunch novels, however.
At first it wasn't certain that the captain on this show would be black, and Richard Dean Anderson was considered for the lead. (One wonders what would have happened to Stargate SG-1 if they had decided otherwise...) Alexander Siddig originally tried out for the part of Sisko, but was turned down for being too young. Peter Capaldi and Anthony Stewart Head also auditioned for the role.
Later, when they decided that the character would be black, James Earl Jones, Tony Todd and Carl Weathers were each approached. Had Jones been cast, the character would have been an admiral, and Jake would have been his grandson.
Bashir, the Scrappy in residence, was nearly axed from the show numerous times. Siddig didn't even know about this until well into the fourth year.
Melora from "Melora" was meant to be the station's chief science officer, but this proved impossible due to problems with portraying zero gravity. It was possible, however, to feature her as a one-off character. In the novel 'verse, she would eventually become head of stellar cartography on the Titan.
According to rumor, the showrunners considered making Gul Dukat a member of the main cast. Alaimo was all for it, but it was shot down by Ira. ("I don't want him to become the friendly neighborhood Cardassian.") If this idea were used, the ending of the show probably would have been vastly different. Instead, Dukat remained an enemy commander who frequently cons the DS9 gang into working with him.
Clint Howard's part in "Past Tense" was originally going to be Iggy Pop, but he wasn't yet available.
Tim Ransom (Jack the Augment) had previously auditioned for a number of roles in Star Trek unsuccessfully, including that of Bashir.
Hilary Shephard Turner (Lauren) also tried out for the role of Jadzia. This is referenced in "Chrysalis" when she turns up in a Starfleet sciences uniform. Alarmingly, she is a dead ringer for the dearly departed Trill!
T'Rul (Martha Hackett), the Romulan woman mandated by her government to supervise the Defiant's cloaking device, was supposed to stay on for more episodes. The writers didn't know what to do with her or what role she could have beyond the cloaking device, so T'Rul vanished, and Hackett ended up in a recurring role on Voyager as Seska.
Ira Behr tried and failed to get a Vic Fontaine-like character onto the show for years. Frank Sinatra Jr. was approached first, but as he would be playing a Rat Packer jazz artist (essentially his father), he wasn't interested in that sort of role. Robert Goulet and Tom Jones also turned the part down.
Vic Fontaine was also supposed to get a physical girlfriend, but they never found the time for that plot.
Molly Hagan was meant to reprise her role as Eris for "The Search" and later "The Ship," but was unavailable for both occasions.
Just like with Voyager's premise, ideas were pitched around on how to soft reset DS9 into a traditional Star Trek show if the fans didn't take to it. This might be why "Emissary" established that the station is capable of reducing its mass in order to move; according to Behr, it was suggested that the crew strap engines onto DS9 and fly into the wormhole.
Other spitballed ideas, according to Moore, were blowing up Bajor or removing the crew from DS9 in some way. (Berman hatched the idea of bringing back Worf to shut the executives up.)
The Borg were originally considered for the main villains of the show, hence their appearance in the pilot. But their uber-power which prevented them from regularly appearing on TNG convinced the writers to can the idea. Their appearance in the pilot is all that is left. VOY didn't get that memo: The Borg appear in mid-Season 3 and would go on to become the over-arching villain of that series, with many considering it a major example of Villain Decay.
The Klingons and Romulans were also briefly considered for the main villain role. While the idea of Klingons returning to their more villainous roots was explored briefly in the middle of the series, the Romulans never ventured far beyond their Wild Card role.
Ronald D. Moore wanted to reintroduce the Tholians as major antagonists, which got the support of the entire writing staff. However, special effects limitations convinced them they could not portray the Tholians without them looking ridiculous, so the idea was canned. Similar concerns had previously prevented them from appearing on TNG, where they also had serious support for a re-appearance. It wouldn't be until 2005 on Enterprise where they would finally re-appear.
Paradoxically, Ronald D Moore (and the entire writing staff, according to him) was adamantly against reintroducing other iconic TOS races such as the Andorians, Tellarites, and Gorn, presumably as they were seen as irredeemably corny. They too would have to wait until Enterprise for their return. Robert Hewitt Wolfe on the other hand claims there was support among writers to bring back the Andorians, but they were not allowed to (presumably by Berman and Moore).
The Andorians would be explored extensively in the DS9 relaunch novels, through the character of science officer Thirishar "Shar" ch'Thane.
In the TNG crossover "Birthright", Dax was slated to film some scenes on the Enterprise-D set with Data, but a scheduling conflict dashed that idea. Bashir went over in her place. The episode she filmed instead? The execrable "Move Along Home". According to Terry Farrell (a lifelong Trekkie), she "cried."
In an early version of what would become "Invasive Procedures", Dax's symbiont becomes ill and Bashir has to temporarily remove it. With Dax gone, all that's left is the original Jadzia who—irony—falls hard for Dr. Bashir. The episode would have ended with Bashir trading his chance at love to keep Dax joined.
The writers originally toyed with the idea of killing off Jadzia Dax in the Season 6 episode "Change of Heart" rather than in "Tears of the Prophets", the season finale. The idea was that Jadzia would manage to convince Worf to continue their mission without her and leave her behind, in which case she certainly would have died. Worf would then have had even more angst than he ended up with to work through in the final season, having lost his wife out of choosing his career over her. Terry Farrell (Jadzia) was on board with it, but they ended up not going through with the idea.
Terry was contacted about reprising her role in "What You Leave Behind" (presumably in a scene with Ezri). The price her agent quoted was too prohibitive, and the scene was cut. The producers then meekly asked to use old footage of Jadzia for the montage at the end. No dice. But Terry did turn up for the DS9 wrap party.
Leonard Nimoy expressed an interest in reprising Mirror Universe Spock in an episode.
Michael Dorn was to appear as mirror universe Worf in the season 2 episode 'Crossover', two seasons before Worf would become a regular on the show, but Dorn was shooting the TNG finale at the time. His lines were given to Andrew Robinson as Mirror!Garak, who was only supposed to have a minor appearance.
The Dominion were originally conceived as an "anti-Federation", an actual alliance of different, more or less equal species, who believed in conquest and expansion instead of exploration and understanding. Because of budgetary reasons and other concerns, the idea was radically re-worked into an empire clearly led by one race, though the Cardassians and the Breen joining later in the series echoes this original idea, as do the Xindi over on Star Trek: Enterprise.
The Vorta were originally going to be space traders instead of diplomats; sort of rugged, "Brian Dennehy or Bob Hoskins" looking types. Robert Hewitt Wolfe elaborated that his Vorta were arms dealers, the guys who supplied tanks, or guns, or genetically-engineered soldiers like the Tosk. That idea led to the Vorta being bred from hatcheries themselves.
Initially it was Vulcan, not Betazed that was conquered by the Dominion during "In the Pale Moonlight", but the writers nixed that because they felt it would offer Sisko too much justification for the extreme measures he then undertook. Ironically, J. J. Abrams would happily blow Vulcan to smithereens in the 2009 movie. In an even more ironic decision, he blew Vulcan to smithereens for precisely the same reason that Ron Moore didn't have it occupied: it showed how serious things were, and that things were not going to be the same again.
The tension between the original Jem'Hadar from the Gamma Quadrant and the new "Alpha" Jem'Hadar was supposed to be a running plot thread, but it got dropped and "One Little Ship" ended up being the only episode to mention the two varieties of Jem'Hadar.
Ronald Moore originally wanted to name the Defiant "Valiant", but this was rejected out of fear people would confuse it with Voyager. The name Valiant was eventually used for one of the Defiant's sister ships.
Robert Hewitt Wolfe planned to end "Second Skin" on an Ambiguous Clone Ending, with Bashir unable to determine whether Kira is actually a Cardassian. This left open the possibility that Kira was unknowingly a Cardassian agent all along, and that the Obsidian Order had been telling the truth.
Originally, Jack, not Sarina, was the one who was going to be 'cured' in "Chrysalis". Behr decided that the story lacked bite, and sent a message that quirky or handicapped people need to be fixed. So Sarina underwent the treatment instead. She gains a normal life but loses the companionship of her friends, who are still 'in treatment' (imprisoned) at the Institute.
"Homefront" and "Paradise Lost" were planned originally as the season three finale and season four opening, respectively. The plot was somewhat different, with groups of Founders infiltrating the Federation and causing a near-civil war, with Vulcan seceding from the Federation, and "Homefront" ending with a Starfleet vessel firing on a Vulcan transport in Earth orbit. However, Paramount decided to boost ratings by introducing a Klingon storyline and adding a TNG regular (they settled on Worf) to the main cast.
While "Trials and Tribble-ations" is regarded as one of the best episodes of the series and a fitting 30th Anniversary for the franchise, there were numerous other ideas which were tossed around. One was the return of Enfant Terrible Charles Evans from the TOS episode "Charlie X", most likely seeking revenge in a manner similar to Barry Waddle. Another was having the Deep Space Nine crew visit the mobster planet from "A Piece of the Action", where they find that the inhabitants have gone on to emulate Starfleet as a commentary on Star Trek fandom.
Remember how a crewmember of the USS Sutherland performed a fire-dance at Jadzia's bachelorette party in "You Are Cordially Invited"? Well, they initially had expanded plans for the Sutherland- many of the other crewmembers would've carried on Hawaiian and/or Polynesian traditions, and they would've appear whenever plans called for "wacky party guys". But for whatever reason, that didn't pan out.
The decision to ship Kira to Cardassia had a domino effect on the rest of the seventh season. Garak went along as backup, and Ira Behr didn't want to split Kira and Odo up, so Odo went, too. Originally, Odo was going to spearhead the search for a cure for the Changeling plague, culminating in a reunion with his "father" Dr. Mora who was actually responsible for engineering the virus as a weapon. The writers knew they would never have time to do this storyline justice, so Bashir and O'Brien went looking for a cure instead.
The writers wanted to do another episode with Laas, specifically to address the fact that he contracted the virus Odo had after linking, but there was no time, and it never happened.
"In the Pale Moonlight" originally was to focus on Jake trying to interview Garak and thrown by the man blowing him off. Jake would dig deeper to discover Garak and Sisko's plot to trick the Romulans into war. Jake would try to publish the report but Sisko would refuse to let him. The writers soon realized they just couldn't make the father vs son conflict work right and the episode was retooled to focus on Sisko.
The episode "Valiant" would have had Jake be paired with Kira, however this was changed as they realized that had Kira had been there, she would have kicked ass, took names, and hauled the cadets and the Valiant back to Federation space.
Originally the prophecy that Sisko would 'find no peace on Bajor' was supposed to mean that he would wish to retire there but, in order to save it, would never be allowed to live there (thus why Sisko constantly talks about building a house there in the finale season). After the writers realized this was a weak payoff, they changed it: "Find no peace" now referred to Sisko's marriage to Kassidy (which originally the Prophets had no issue with). However, this created another issue; see below.
The finale originally was filmed to make it clear Sisko was never coming back. He had ascended to a higher plane and, for doing his duty, had to leave his old life behind forever. After they finished filming, Avery Brooks worked up the nerve to express his concern: it didn't look good that a black man was abandoning his pregnant wife. The writers quickly realized their mistake but with so much filming already done all they could do was add a quick line making it clear Sisko would return.
Movies and spinoffs
The cast hoped there would be a movie spinoff at some point (the TNG films still being successful at the time of DS9 ending) but the failure of Nemesis put paid to that idea (the planned sequel to Nemesis actually was to feature a crossover between Deep Space Nine, Voyager and The Next Generation in a grand finale to the TNG era in general, but of course it never happened).
Any hopes of resurrecting the project would seem over: the actors have all seriously aged out of the roles (at the time of writing, it's been fourteen years since the show went off the air). The 2006 auction at Christies where a huge number of props (including the "hero" model of the station itself), costumes and other items from the series were sold off made it even less likely and the 2009 reboot of the entire Star Trek franchise would seem to be the final nail in the coffin. One person who doesn't seem to mind is Alexander Siddig, who believes DS9 deserved to be "put to bed". Nana Visitor, however, thought the show had a lot more mileage left. (Mostly, though, she wishes she could have had one year of running the station!)