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.
Originally, Dax would have been depicted using the same makeup and prosthetics as Odan from "The Host." In fact Terry Farrell was already fitted for the prosthetics and the makeup was tested in early filming. However Executive Meddling by Paramount lead them to ditch the makeup, because the studio didn't want to have Farrell covered up in a form of Shoot the Money; They paid for a hot actress, and dammit they were going to show a hot actress.
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.
Kim Cattrall was offered the role of Kira, but turned it down.
Kathy Bates was considered for the role of Kai Opaka, however she did not do television projects at the time.
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 because portraying zero/reduced gravity was ultimately too much trouble for them to do it on a regular basis, so she was relegated to 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.
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.
Malcolm McDowell, who had been played the Big Bad in Star Trek: Generations, once said he'd like to appear in the series, but only if his nephew - Alexander Siddig - would direct the episode. He was offered the role of Hagath in "Business as Usual", but he was unavailable. The role went to Steven Berkoff, McDowell's costar in A Clockwork Orange. Siddig was subsequently banned from directing any future Star Trek episodes following the extremely negative reception of the next episode he directed, "Profit and Lace", ending any chance of McDowell making an appearance in the series.
Molly Hagan was meant to reprise her role as Eris for "The Search" and later "The Ship", but was unavailable for both occasions.
David Warner was approached by the producers for the role of Akorem Laan in "Accession". According to Ira Steven Behr, Warner wanted to do the role, but his wife talked him out of it, as they were on a vacation.
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. (Given that their role as an Arc Villain in VOY led to a line of development that is frequently considered a major example of Villain Decay, it was probably for the best.)
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, 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.
Dax was originally envisioned as an alien from a low-gravity world forced to get around in a wheelchair and who flew around her quarters. The concept was scrapped because the "flight" cables were too difficult to rig. However, the idea was revisited for "Melora".
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, which allowed them to set it up a little bit differently. Even then, we see the character struggle with the effects; she gains a normal life, but loses the only friends she'd had, and because she's been cut off from the world for so long, she doesn't really fit in with those people either.
"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.
Guinan was supposed to cameo in "Rivals" (where Martus Mazur would be revealed to be her wayward son), but Whoopi Goldberg had to turn it down as it conflicted with the filming of other projects. All references to Guinan were then removed from the script.
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. In fact, a large part of the reason they decided on using "The Trouble With Tribbles" was down to random chance; they were talking about the project at a pizza place and were discussing which guest stars from the original series they might be able to get, only for Ira Steven Behr to suddenly realize that Charlie Brill (Darvin) just happened to be in that exact pizza place at that exact moment.
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 in the original plan, 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 Odo ended up remaining on the station, with Bashir and O'Brien tackling the search 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.
The original concept for "Second Skin" involved O'Brien finding out he was (for real) a deep-cover Cardassian agent; this version stalled when the writers realized that this would be incongruous with O'Brien having a fully human child (Molly). The story was therefore rewritten to feature Kira, and an additional edit changed this into a deception, with the ending revealing that she is in fact Bajoran.
"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" originally would have had Jake be paired with Kira, however this was changed as they realized that Kira would never have allowed the events of the episode to play out the way they did.
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.
In The Collaborator, the producers originally intended Bariel become Kai, but they decided that would be a waste when they could have the treacherous Smug Snake Winn rise to that position, setting her up as a much more powerful recurring antagonist.
In the DS9 documentary What We Left Behind, Ira Stephen Behr acknowledges that the series could have done much better with explorations of sexual identity, and suggests that Dr. Bashir and Garak's rapport could have built into something more, specifically that Garak should have come out to him as "a gay Cardassian" after the events of season 2's "The Wire." Yet while there are stories of Executive Meddling telling Siddig and Robinson to tone down the Ho Yay in their scenes together, in this case the idea of making Garak explicitly queer just did not occur to the writers at the time, according to Behr.
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!)
The 2019 deaths of Aron Eisenberg (Nog) and René Auberjonois (Odo) pretty much eliminate any remaining chance of this. While it might be possible, though jarring, to work around the absence of Odo, who left to join the other Changelings at the end of "What You Leave Behind", it would be much more difficult to explain or work around Nog not being there, since his position on the station was only solidified in the finale.