在接下來的一個賽季，在布朗教練的帶領下，馬刺隊從最差的球隊一躍成為最好的球隊。大衛-羅賓遜在1989年5月19日結束了他的兵役。9天之後，馬刺隊用羅伯特森和“凱迪拉克”格雷格-安德森，從密爾沃基雄鹿隊換來了特-康明斯。在1989年的選秀中，聖安東尼奧在第三順位選擇了肖恩-埃利奧特。這個夏天稍晚一些的時候，在一個牽涉到5名球員的交易中，強尼-道金斯被送到76人隊，而莫斯-奇克斯加入馬刺。在賽季開始的時候馬刺的陣容麵有了9張新麵孔。聖安東尼奧在1989－90賽季的揭幕戰中以106比98擊敗了湖人隊。在他NBA的處子秀中，羅賓遜砍下23分和17個籃板。聖安東尼奧在11月8勝5負，之後在12月取得11勝2負並登上了中西部的榜首。在2月21日，馬刺隊又完成一筆交易，用奇克斯從紐約尼克隊交換來了控球後衛羅德-斯特克蘭。聖安東尼奧以56勝26負結束賽季並以一場的優勢力壓猶他爵士排名第一。1989－90賽季比1988－89賽季多贏35場比賽的成績也是NBA曆史上球隊勝場進步最大的紀錄。而這個巨大轉變的驅動力就來自“上將”羅賓遜。羅賓遜在賽季的每個月都拿下了月度最佳新秀，而且他24.3分和12.0個籃板的數據在球隊中均排名第一。他被選為年度最佳新秀並入選了西部全明星陣容。西部半決賽對陣波特蘭開拓者隊，馬刺在第7場加時賽中105比108落敗。

    馬刺隊證明了他們在1989－90賽季的表現不是個意外，他們在接下來的賽季中力壓猶他爵士隊，連續第二年獲得中西部分區的冠軍。球隊取得55勝27負的好成績。馬刺隊以NBA總冠軍有力爭奪者的姿態進入到季後賽。但球隊在同金州勇士隊的首輪比賽中就遇到了挫折。3名馬刺球員得分超過30，幫助球隊在主場以130比121拿下第一場，但勇士隊拿下了隨後的3場比賽，並贏得整個係列賽。聖安東尼奧在隨後的休賽期中完成了一筆大交易，用德文-辛奇祖斯從薩克拉門托換來了6尺9寸高的壯漢安東尼-卡爾。球隊的先發控球後衛斯特克蘭由於和球隊在合同上有爭議而在賽季開始的時候被摁在板凳上，直到12月末才重新上場。盡管缺少了先發控球後衛，馬刺隊還是在1991－92賽季中，在11月份打出了10勝3負的開局。但球隊在隨後的兩個月中表現不佳，主教練拉-布朗也在1月21日辭職。當時正擔任球隊運作方麵的副總裁的鮑勃-巴斯，在17年中第四次臨危受命，出任球隊主教練。在巴斯的帶領下，球隊在賽季後期打出26勝18負，使得他們總成績達到47勝35負，這也足夠確保他們僅僅落後爵士隊而排名中西部分區的第二。但馬刺隊在季後賽中有所作為的希望由於羅賓遜和威利-安德森的缺席而變得渺茫起來。“海軍上將”在經曆了左手的韌帶修複手術後，於4月1日被球隊放入傷病名單中。安德森則由於他的左脛骨的應力骨折而缺席了賽季的最後24場比賽。在季後賽開始的時候，他們2人都無法出場，而馬刺也因此在首輪中被菲尼克斯太陽隊橫掃。在新賽季開始前馬刺隊請來了傑-塔坎尼安成為他們新的主教練。10天之後，塔坎尼安短暫的執教在持續了6周後就宣告結束。他隻留下了9勝11負的戰績。約翰-盧卡斯隨後被授予主教練的職責。馬刺隊在這名前NBA後衛的帶領下打出了靈氣十足的比賽，在他接手後的18場比賽中贏下了其中的16場。球隊一個重要的變化是在先發陣容中增加了5尺10寸的控球後衛埃弗-約翰遜。作為盧卡斯教練以前在西雅圖時的隊友，“A.J.”在他為馬刺打先發的前12場比賽中平均每場得到11.4分和9.9次助攻，並幫助球隊取得11勝1負。季後賽第二輪對陣太陽，馬刺讓菲尼克斯人驚出了一身冷汗。太陽隊在菲尼克斯的第五場比賽中以109比96擊敗了馬刺。第六場比賽是在馬刺主場半球球館進行的。在100平之後，太陽大前鋒查爾斯-巴克利在比賽還剩下1.8秒時命中了18尺外的跳投，之後大衛-羅賓遜未能命中20尺外的壓哨跳投，馬刺隊被淘汰出局。這也是在半球球館進行的最後一場比賽。馬刺隊在1993－94賽季搬到了嶄新的阿拉莫球館。

    在新賽季開始前馬刺隊用肖恩-埃利奧特從底特律活塞隊交易來了丹尼斯-羅德曼。在整年中不停的變換頭發顏色的羅德曼給馬刺隊在1993－94賽季帶來了完全不同的變化。在羅德曼加盟後，上個賽季在進攻籃板上排名倒數第一的馬刺隊一躍而攀升到了正數第一。然而，羅德曼起到的更加顯而易見的影響是使得大衛-羅賓遜減少了爭奪籃板球的壓力從而能有更多的機會去得分。在賽季的最後一天，羅賓遜在對陣洛杉磯快船隊的比賽中砍下70分，生生地從沙奎爾-奧尼爾手中搶過了得分王的頭銜，這也使得他成為了NBA曆史上第四名在單場比賽中得分超過70分的球員。他還在2月17日對底特律的比賽中創造了另外一項NBA的記錄，34分、10個籃板、10次助攻和10個蓋帽的成績使得他成為了又一名拿下四雙的球員。場均17.3個籃板的羅德曼與羅賓遜在NBA曆史上在同一個賽季的得分和籃板的個人統計上同時分別排在第一。馬刺隊以55勝17負的成績落後休斯敦火箭隊排名中西部分區第二。但是在以3勝7負結束他們最後10場常規賽之後，馬刺隊在同猶他爵士隊的季後賽中首輪比賽中繼續前進的動力。猶他連下四城，而馬刺在這個係列賽中平均每場僅得到88.0分。幾周之後，盧卡斯離開聖安東尼奧，前往費城76人隊擔任總經理兼主教練。1994－95賽季成為了馬刺隊有史以來最出色的一個賽季，雖然對於馬刺隊的球迷們來說它結束的稍微有些太早了。球隊打出了62勝20負的戰績，在NBA排名第一並且這也是球隊曆史上的最佳戰績。馬刺隊上一個最好的戰績是在1989－90賽季的56勝26負，而那也是大衛-羅賓遜的新秀賽季。這個賽季的開局並不理想。在羅德曼禁賽的情況下，聖安東尼奧跌跌撞撞地取得了7勝9負的成績。但馬刺隊在其後的比賽中打出了55勝11負，其中包括了2次的15連勝。他們在常規賽的最後23場比賽中取得了21勝2負。球隊在2、3、4月份分別獲得了11勝2負、14勝2負和11勝2負，並隨之獲得中西部分區的冠軍。多名球員取得了優異的表現，羅賓遜場均27.6分、10.8個籃板、3.2個蓋帽榮膺MVP。在和底特律活塞隊進行的交易中，馬刺用選秀得到的比爾-柯利換來了舊將肖恩-埃利奧特，而他也為馬刺的進攻作出了巨大的貢獻，場均得到18.1分並且出手三分333次，命中136個，40.8%的三分命中率在NBA排名18。羅德曼外表看上去依舊獨一無二，而他的籃板能力也依然無人能及。盡管錯過了33場比賽，他還是連續第四年拿下籃板王（16.8個）並且入選NBA第三陣容以及NBA防守第一陣容。季後賽中，馬刺隊在第一輪橫掃了丹佛掘金隊，4比2擊敗了洛杉磯湖人隊，然後在與休斯敦火箭隊進行了6場西部決賽後敗下陣來。