罗宾逊在被马刺选中后先去海军服役两年再归队。
酝酿:海军上将初长成
“幸福会给能等的人敲门”--罗宾逊是这句谚语的真实写照。1987年，罗宾逊在美国海军学院取得了数学学位，而他在被马刺选中之后，选择在海军服完2年兵役再正式在NBA打球。
罗宾逊是海军学院篮球史上最出色的人物。但身高1.93米的他只有一年的篮球经验，加入球队的第一年他场均只有7.6分、4篮板进账。不过在海军学院上学期间他的身高长高了接近18厘米，他也开始变得甚具破坏力。
在大三那年，罗宾逊场均能有22.7分(比大二的23.6分有所下降)，13个篮板领跑NCAA联盟，他也凭借5.91个盖帽刷新了联盟分区的历史记录。罗宾逊曾在一场比赛中贡献了14个盖帽，创造了校队队史的新纪录，而他单赛季207个盖帽也是领跑队史。到了大四他的场均数据飙升至28.2分、11.8篮板和4.5盖帽，他也众望所归赢得了年度最佳球员。在学校生涯的谢幕战，罗宾逊以50分个人得分划上了句号，不过球队还是输给了密歇根大学。
1988年罗宾逊代表美国队参加了奥运会并取得了铜牌，那是美国男篮最后一次在奥运会上全部以非职业篮球运动员组队参赛。
1987年的选秀中，罗宾逊无疑是最出彩的球员，但是他还有为海军服役的义务，这使得他在1989年才能开启自己的NBA职业生涯。马刺在那年获得了状元签，摘走了罗宾逊，在看了看他在大学时期的表现，圣城认为值得等他2年。
“海军上将”用生涯前3年时间奠定了自己的地位。
归来:闪耀生涯初期
1989-90赛季，24岁的罗宾逊终于迎来自己的菜鸟季。作为当时联盟最具天赋以及最全能的球员之一，“海军上将”在菜鸟季的6个月都占据了月度最最佳新秀，当然他在赛季结束之后也轻松拿走了年度最佳新秀的奖项;而在赛季中段他也入选了全明星。
在职业生涯的第一年，罗宾逊场均数据能达到24.3分、12篮板和3.89个盖帽，投篮命中率53.1%。他在每项数据上几乎都刷新了队史新秀的最佳纪录，同时曾46次获得球队单场最高得分、61次获得单场最高篮板数。当时马刺只有两名球员能全勤打满82场，罗宾逊就是其中之一，他的得分排在了联盟得分榜的第10位，篮板排在第2，盖帽排在第3。那个赛季对森林狼的一场比赛中，他单场贡献12个盖帽刷新了职业生涯最高，而在赛季结束之后，他入选了联盟最佳防守阵容二队。
罗宾逊在新秀季的巨大成功，是马刺队在一年内取得NBA历史上最大进步的主要原因。在1988-1989赛季，马刺的战绩是21胜61负，然后他们在选秀中招来了肖恩-埃利奥特，通过交易得到特里-卡明斯和罗德-斯特里克兰，此时罗宾逊也服完兵役归队了。在这样的阵容底下，马刺在接下来的那个赛季多赢了35场球，战绩升至56胜26负，并且获得了中西部分区的冠军。马刺还闯进了西区半决赛，但是经历7场鏖战之后败给了开拓者。
“海军上将”在季后赛打出了闪耀的表现，他在10场季后赛中场均有24.3分、12篮板和4盖帽的数据。
在职业生涯的前3年，罗宾逊便在联盟最佳球员之中建立了自己的地位。在早期他获得的荣誉包括:1991年和1992年连续入选联盟第一阵容、1991年防守一阵以及1992年获得年度最佳防守球员荣誉。
波折:伤病无碍走向巅峰
不过罗宾逊生涯第3年的结局是让人失望的，他在当年3月17日的比赛中左手韧带撕裂，这个伤病不得不让他缺席了剩余的常规赛以及整个季后赛。在罗宾逊赛季报销之后，马刺陷入挣扎，在余下的常规赛中5胜9负，然后在季后赛首轮被太阳横扫出局。
尽管那个赛季并不完美，但是罗宾逊还是加入了克里夫-哈根和拉里-伯德的行列，成为了联盟史上第3位能在单赛季5项数据均排进联盟前十的球员。那个赛季“上将”场均23.2分排在第7、12.2个篮板排第4、4.49个盖帽第1、2.32个抢断第5、投篮命中率55.1%第7。罗宾逊也是史上第一位单赛季能在盖帽和抢断都排进联盟前5的球员。
“海军上将”的优异表现为他赢得了连续第2年入选联盟第一阵容的荣誉，他也连续3年入选了全明星，而让那个赛季最大的亮点就是他获得年度最佳防守球员。
赛季结束后，罗宾逊入选梦一队，前往巴塞罗那征战奥运会。梦一队可谓星光熠熠，他的队友不乏迈克尔-乔丹、“魔术师”约翰逊和伯德这样的球星，最后他们协力夺得了奥运金牌。
到了生涯第4个赛季，罗宾逊成为了马刺的顶梁柱。他打满了82场，总出场时间3211分钟创下了当时的队史记录。那个赛季罗宾逊场均23.4分、11。7篮板、3.22盖帽、1.55抢断，入选了联盟最佳阵容三队和最佳防守阵容二队。同时，他连续第3年被球迷投进了西部全明星首发，并且在全明星有21分、10篮板的表现。
不过不幸的是，马刺在季后赛西部半决赛遇到了当时最强的球队--由查尔斯-巴克利领军的太阳队。虽然罗宾逊在季后赛能有场均23.1分、12.6篮板的表现，但是最后凤凰城还是用6场比赛的时间把马刺淘汰了。
罗宾逊的技术达到了最娴熟的阶段，他在场上奔跑着看起来不像是一名7尺中锋(约2.13米)，他能抢得防守篮板，然后迅速加入快攻中，用一个震撼人心的扣篮来结束一个回合。在半场进攻方面，罗宾逊也有非常柔软的跳投手感。“海军上将”已经得到联盟认可为最佳球员之一，而他也在1993-94赛季打出了最出色的表现。
