I believe DS9 was greenlit somewhere around 1990 or 1991. Origins for the ideas of it go as far back as late 80s when TNG started to be successful. The Maquis/Cardassian/Bajoran stuff was written around that time(90 or 91) to lead up to DS9. I think Ensign Ro was going to be introduced to be Kira's role of the 2nd officer of DS9 but she declined so they changed it to Kira/Nina. DS9 was the last thing Gene Roddenberry gave the go ahead on.