起源
印第安納步行者隊於1967年組建於印第安納波利斯(Indianapolis，印第安納州首府)，加盟當時的ABA(美國籃球協會，American Basketball Association)。
第一版的隊標確切地說，步行者隊名Pacers可能譯作溜馬隊或者溜車隊更加恰當。因為根據當時的八位投資者之一、律師出身的理察-廷克漢姆(Richard D. Tinkham)介紹，這個名稱的由來有兩個原因：首先是因為輕駕馬車比賽(harness racing pacers)在印第安納州有著悠久的歷史，而投資人之一的查克-巴恩斯(Chuck Barnes)本身就是一位狂熱的賽馬迷；另一個原因是因為印第500(Indianapolis 500，美國享有盛譽的汽車賽事)所用的領跑車就叫作pace car。
廷克漢姆還介紹說，當時Pacers這個名字很快就定下來了，爭論的焦點反而集中在應該叫印第安納波利斯步行者(Indianapolis Pacers)還是印第安納步行者(Indiana Pacers)。最後因為當初的構想是球隊雖然以印第安納波利斯市為根，但是要在整個州內打比賽，所以球隊正式命名為印第安納步行者。
印第安納步行者在1976-77賽季同其它三支ABA球隊一起併入了NBA。這支三次ABA總冠軍得主在加盟NBA伊始，慘澹經營，頭13個賽季只有一次勝率超過百分之五十。經過長達15年的摸索，球隊戰績終於在九十年代初有所起色。到了九十年代中期，他們已經成為東部賽區的一支勁旅。從1994年到2000年，步行者隊五次進入東區決賽，兩次奪得中部分區冠軍，並於2000年殺入NBA總決賽。
在步行者隊1967-68的首個ABA賽季之前，印第安納波利斯已經有過兩支NBA球隊。印第安納噴氣機隊(Jets)只打了1948-49一個賽季就慘澹收場，戰績是可憐的18勝42負。下一個賽季印第安納奧林匹亞人隊(Olympians)粉墨登場，他們以39勝25負的戰績取得了NBA西部分區的冠軍。奧林匹亞人隊打了四個賽季，於1953年解散。
印第安納州一直以來就是一個籃球重鎮，當地民眾對各中學籃球隊以及印第安納大學的校隊印第安納人隊(hoosiers。譯者註：這是印第安納州本地人給自己取的綽號)一向給予全力支持，特別是在七八十年代，印第安納人隊在主教練鮑勃-奈特(Bob Knight)帶領下取得了成功之後。正因如此，各職業聯盟自然而然地十分垂涎這個市場。於是在1967年，八位商人每人出資幾千美元組建了步行者隊，正式加入了ABA聯盟。
1967-1976：榮耀的ABA時期
1967-71 布朗和丹尼爾斯：步行者的先驅們
先行者羅傑-布朗步行者隊簽的第一名隊員就是羅傑-布朗(Roger Brown)，他是被人從工廠車間裡拎出去簽約的。布朗後來成為了步行者隊歷史上最富傳奇色彩的明星。
經過了令人失望的第一個賽季，步行者隊在主帥鮑勃-萊昂納德(Bob Leonard)的帶領下在隨後的七個賽季中取得了驕人的戰績。萊昂納德在步行者隊執教了十二個賽季。1968-69賽季他首次執掌帥印就率隊取得了44勝34負的佳績。該賽季步行者隊攻勢犀利，場均得分119.6分，這個球隊紀錄一直保持至今。
當時步行者隊球星雲集，最著名的要數二年級中鋒梅爾-丹尼爾斯(Mel Daniels)。丹尼爾斯場均24.0分16.5個籃板，並當選為ABA這一年的MVP。丹尼爾斯6尺9寸、225磅，前一個賽季效力於明尼蘇達Muskies隊(後來遷至邁阿密)。Muskies隊用丹尼爾斯向步行者換來了12.5萬美元現金和兩名球員——吉米-道森(Jimmy Dawson)和羅恩-科茲利奇(Ron Kozlicki)，然而這兩名球員隨後便退出了職業聯賽。
步行者隊在68-69賽季初狀態低迷，5勝15負。但是他們成功翻盤，贏得了東部分區冠軍，並在季後賽中擊敗了肯塔基上校隊(Kentucky Colonels)和邁阿密佛羅里達人隊(Miami Floridians)進軍ABA總決賽。可惜在總決賽中以1比4負於奧克蘭橡樹隊(Oakland Oaks)，與總冠軍失之交臂。
1969-70賽季步行者隊乘勝追擊，攻勢如潮，取得了59勝25負的佳績。在4月12日對匹茲堡Pipers的比賽中，他們狂砍177分，這也是ABA歷史上的最高得分紀錄。步行者隊在ABA東部分區排名第一，季後賽中分別淘汰了卡羅萊納美洲豹隊(Carolina Cougars)和肯塔基隊進軍總決賽。在ABA總決賽中步行者隊以4比2擊敗了洛杉磯明星隊(Los Angeles Stars)贏得總冠軍。布朗在關鍵的總決賽第六場斬獲45分，包括7個三分球。
該賽季中，布朗拿到了職業生涯最高的場均23.0分，成為隊中的得分王。丹尼爾斯也不甘人後，搶下場均17.6個籃板，並被選入ABA最佳陣容二隊。在其後的25年多的時間裡，丹尼爾斯職業生涯的場均19.5分和15.9個籃板一直是步行者隊的一個紀錄。
1970-71賽季ABA進行了重新分區，步行者隊被分到了西部分賽區。該賽季他們取得58勝26負，並贏得了西部分區冠軍，但是在季後賽當中被猶他明星隊(Utah Stars)淘汰。他們在這個賽季中再次高舉進攻的大旗，場均得分119.1，也是球隊歷史上第二高的成績。丹尼爾斯場均貢獻21.0分和18.0個籃板(步行者隊單賽季的紀錄)，第二次當選ABA的MVP。而他也和布朗同時入選ABA最佳陣容一隊。
1971-74 麥金尼斯加盟，步行者如虎添翼
1971-72賽季，步行者隊常規賽的47勝37負儘管只能說差強人意，但他們仍然奪得了第二個ABA總冠軍。印第安納大學二年級新秀喬治-麥金尼斯(George McGinnis)的加盟，讓步行者隊如虎添翼。在12月29號對佛羅里達人隊的比賽中，丹尼爾斯一舉摘下了創紀錄的26個防守籃板。季後賽中步行者隊如履薄冰，先後苦戰7場淘汰了丹佛火箭隊(Denver Rockets)和猶他明星隊，然後在總決賽中4比2擊敗巨星里克-巴里(Rick Barry)領銜的紐約籃網隊(New York Nets)，捧走了總冠軍獎盃。
1972-73賽季，步行者隊蟬聯了ABA總冠軍。他們常規賽戰績是51勝33負，其中包括一個11連勝。印第安納僅在西部分區排名第二，次於猶他明星隊。但這並不能阻止他們在季後賽所向披靡，在總決賽中4比3擊敗肯塔基奪冠。麥金尼斯榮獲總決賽MVP稱號，這是對他本賽季的出色表現的一個肯定。麥金尼斯常規賽場均27.6分，並在11月28號對達拉斯叢林隊(Dallas Chaparrals)的比賽中狂撈58分，這個步行者隊單場得分紀錄一直保持到現在。
在這幾個輝煌的賽季之後，步行者隊的成績開始滑坡。1973-74賽季常規賽段球隊表現尚可，46勝38負，但是季後賽被猶他淘汰。麥金尼斯則繼續統治著比賽。在1月12號對卡羅萊納美洲豹的比賽中，他摘下了37個籃板，一舉打破了此前由梅爾-丹尼爾斯於1969年創下的單場31個籃板的紀錄。
1974-76 新球場——市場廣場球館
市場廣場球館從1974-75賽季開始步行者隊搬入了新球館——市場廣場球館(Market Square Arena)，其可容納人數為16530人。10月18號球隊在新球館首次亮相，經過兩個加時以121-129負於聖安東尼奧馬刺隊。10月23號，步行者隊122-107羞辱了客場作戰的聖路易隊，取得了在新主場的首個勝利。
該賽季步行者隊45勝39負，在西部分區排名第三。經過了艱辛的季後賽，步行者隊在ABA八年間第五次殺入總決賽。但是他們總決賽的對手、由丹-伊塞爾(Dan Issel)領銜的肯塔基上校隊實在太過強大。最後步行者隊以1比4的總比分飲恨。
本賽季之前，步行者隊用梅爾-丹尼爾斯和弗雷迪-劉易斯(Freddie Lewis)同孟菲斯聲音隊(Memphis Sounds)進行了交易，換來了查理-艾奇(Charlie Edge)和部分現金。少了丹尼爾斯的支持，麥金尼斯肩上的擔子更重。他拿下了步行者建隊至今的賽季場均得分紀錄—29.8分，並和紐約籃網隊的朱利葉斯-歐文(Julius Erving)同獲當年常規賽MVP稱號。新兵比利-奈特(Billy Knight)則入選了ABA該賽季的最佳新秀陣容。比利-奈特在整個職業生涯總共得到了10780分，這也是球隊歷史上的一個紀錄，直到多年後才被雷吉-米勒(Reggie Miller)打破。
到1975-76賽季步行者跌入谷底，無緣季後賽。得分王奈特砍下場均28.1分，蘭-埃爾摩爾(Len Elmore)單季蓋帽178次，遠投手比利-凱勒(Billy Keller)投中了123個三分球(這個紀錄直到90年代才被米勒打破)，後衛唐-布斯(Don Buse)的346個搶斷(場均4.12個)則又是一項球隊紀錄，他也是聯盟該賽季的搶斷王。儘管有著這些出色的個人統計數據，整個球隊的戰績卻不盡如人意，他們在ABA聯盟的最後一個賽季以39勝45負黯然收場。
1976 印第安納的三件退役球衣
ABA聯盟的征戰歲月，不僅催生了步行者隊史上最高的勝率，而且培養出了眾多偉大的球員。當時隊中的三駕馬車—喬治-麥金尼斯(30號)、梅爾-丹尼爾斯(34號)和羅傑-布朗(35號)的球衣也在步行者隊光榮退役。
麥金尼斯在印第安納效力七年，分別是1971-75以及1980-82。他身高6尺8寸，體重235磅，司職前鋒。1975年他和朱利葉斯-歐文共享了ABA常規賽MVP的榮譽，並兩次入選ABA最佳陣容一隊。他是印地安納歷史上總得分第三高的球員，並保持著單場58分和單場37個籃板的球隊紀錄。麥金尼斯在ABA和NBA的職業生涯當中，場均得分20分以上。
丹尼爾斯身高6尺9寸，體重225磅，司職中鋒，在步行者隊效力六年。他兩次當選ABA的MVP，四次入選ABA最佳陣容。在步行者隊效力期間，他為球隊貢獻了場均19.5分和15.9個籃板。布朗是球隊簽的第一個球員。他為步行者打了八年球，場均得分上雙就如同家常便飯 。
布朗6尺5寸，是印第安納歷史上總得分第二高的球員，並保持著球隊單場得分第三高的53分的紀錄。
1976-1987：併入NBA 步履維艱
1976-77 NBA ——當頭棒喝
隨著步行者隊同丹佛掘金隊、紐約籃網隊以及聖安東尼奧馬刺隊一起加入NBA，他們以前在ABA聯盟的所有榮耀就都成了過眼雲煙。NBA的首個賽季對他們來說如遭當頭棒喝。這支ABA當年的霸主在NBA的征戰中就如同一隻菜鳥，步履維艱。
1976-77揭幕戰，步行者隊的對手波士頓凱爾特人隊(Boston Celtics)就給他們上了一課。步行者隊經過加時以122-129負於對手。步行者隊一上來就是三連敗，接著四連勝，然後六連敗，再接著四連勝。戰績雖然差強人意，但也還不算太難堪，直到3月19日他們遇到了金州勇士隊。這場比賽步行者隊慘遭蹂躪，以91-150輸了59分，這是球隊歷史上最慘痛的失敗。步行者隊整個賽季就這樣起起落落，最後36勝46負收官。
儘管球隊戰績平平，比利-奈特卻星光閃耀。一個賽季共投中831球，以場均26.6分成為球隊得分王。約翰-威廉姆森(John Williamson)也場均進帳20分以上。後衛唐-布斯創下每場8.5次助攻的球隊紀錄。奈特和布斯代表印第安納入選了1977年的NBA全明星賽。
1977-80 交易頻仍
1977-78賽季開賽之前，步行者隊交易走了上個賽季的兩位全明星。奈特遠走布法羅勇氣隊(Buffalo Braves)，換來了阿德里安-丹特利(Adrian Dantley)和麥克-班頓(Mike Bantom)。布斯則被交易到了菲尼克斯太陽隊(Phoenix Suns)，換來了里奇-索伯斯(Ricky Sobers)。該賽季步行者隊戰績下滑到31勝51負，包括1月中旬之後的2勝15負。丹特利一度場均26.5分，但是12月他同戴夫-羅比什(Dave Robisch)一起被打包交易到洛杉磯湖人隊，換來了詹姆斯-愛德華茲(James Edwards)、厄爾-塔圖姆(Earl Tatum)和部分現金。隨後步行者隊在1月份用約翰-威廉姆森(當時球隊的二號得分手，場均19.1分)從新澤西籃網隊換來了鮑勃-卡靈頓(Bob Carrington)，而後者下一個賽季便退役了。留在隊中的球員當中，里奇-索伯斯是得分王，場均18.2分。還有其他五名球員也得分上雙。丹-朗德菲爾德(Dan Roundfield)成了籃板工兵，共搶下802個籃板，平均每場10.2個。
1978-79賽季球隊戰績稍有起色，38勝44負。陣容變更不斷，包括朗德菲爾德以自由球員之身加盟亞特蘭大老鷹隊，以及用里克-羅比(Rick Robey)換回了當時在波士頓的比利-奈特。身高6尺1寸的後衛約翰尼-戴維斯(Johnny Davis)是當時隊中的得分王，場均18.3分。索博斯、愛德華茲、亞歷克斯-英格利什、班頓和奈特等人場均都是14.7分以上。在賽季末，加州的百萬富翁薩姆-納西(Sam Nassi)買下了步行者隊。
1979-80賽季球隊戰績37勝45負。為了重塑當年的輝煌，步行者隊用亞歷克斯-英格利什和一個首輪選秀權從丹佛換回了喬治-麥金尼斯。然而這再次被證明是俱樂部的又一昏招。麥金尼斯早已不復當年之勇，只打了兩個賽季便退役。而亞歷克斯-英格利什則是冉冉升起的一顆新星，他後來在丹佛成為了最偉大的攻擊手之一。
1980-83 命運的轉折
1980-81賽季印第安納開始復甦。傑克-麥克金尼(Jack McKinney)從鮑勃-萊昂納德手中接過教鞭，開始了為期六年的步行者隊執教生涯。新官上任的頭三把火燒得還不錯，步行者隊取得了44勝38負的戰績，這是他們加盟NBA以後頭一次整個賽季勝多負少。步行者隊開局不錯，7勝3負，並且將勢頭一直保持到了賽季末，包括1月份的一個七連勝。在他們NBA的第一次季後賽中，儘管直落兩盤乾脆利落地輸給了費城76人隊，但至少他們上升的勢頭是喜人的。步行者隊的陣容中有不少當年輝煌時期的老面孔：比利-奈特依然是得分王，喬治-麥金尼斯回歸，布斯也被召回充當角色球員。但步行者隊早已物是人非，對球隊貢獻更穩定的球員們包括詹姆斯-愛德華茲、約翰尼-戴維斯、麥克-班頓、路易斯-奧爾(Louis Orr)、杜德利-布拉德利(Dudley Bradley)以及克萊門-詹森(Clemon Johnson)。主教頭麥克金尼就在這些球員中不斷試驗著能為他和球隊帶來勝利的組合。因為步行者隊這個賽季的表現，麥克金尼當選為NBA本賽季最佳教練。
然而上個賽季的表現就如同曇花一現。1981-82賽季步行者恢復了菜鳥本色，只取得了35勝47負。他們賽季之初表現尚可，但隨著時間的推移成績逐漸滑落，1、2月份4勝15負，賽季最後21場比賽6勝15負。步行者隊每場平均得分只有可憐的102.2分，在整個聯盟位居倒數第二。讓他們可以聊以自慰的是俄亥俄州大畢業的新秀赫伯-威廉士(Herb Williams)，本賽季共摘下605個籃板。他在包括這個賽季在內的連續六個賽季中都摘下了500個以上的籃板。步行者隊從此開始在中部分區墊底。1982-83賽季他們的20勝62負是球隊歷史上的最差成績。整個賽季印第安納只有兩次取得連勝。在賽季最後三個月的比賽中，步行者隊的戰績是可憐的6勝33負，包括2、3月份的一個12連敗。可以想見的是，球隊的惡劣表現使球迷們失去了興趣。在2月16號對芝加哥公牛的比賽中，觀眾人數只有創紀錄的區區2745人。
1983-84 凱洛格星光閃耀，步行者步履維艱
克拉克-凱洛格新秀克拉克-凱洛格(Clark Kellogg)身高6尺7寸，體重227磅。他是繼赫伯-威廉士之後步行者隊連續第二年選中的前俄亥俄州大球員。凱洛格表現出眾，場均20.1分和10.6個籃板全都是隊中最高的。他入選了NBA新秀最佳陣容(All-Rookie Team)，可惜在年度最佳新秀的爭奪中輸給了聖迭戈快船隊(San Diego Clippers)的特里-卡明斯(Terry Cummings)。比利-奈特(場均17.1分)和威廉士(場均16.9分，171個蓋帽)也都有不俗表現。
1983-84賽季步行者繼續擺爛，戰績是26勝56負。凱洛格和威廉士表現搶眼，但其他隊員都上不了台面。唯一值得一提的只有畢業於密蘇里大學的新秀中鋒史蒂夫-斯蒂潘諾維奇(Steve Stipanovich)。他身高7英尺，體重250磅，場均拿下12.0分和6.9個籃板，併入選了NBA該賽季的新秀第一隊。
1984-87 新東家——西蒙兄弟
1983年球隊老闆薩姆-納西將步行者隊賣給了商廈大亨西蒙兄弟(Melvin and Herbert Simon)。傑克-麥克金尼在1983-84賽季之後交出了帥印，頂替他的是原助手之一，喬治-歐文(George Irvine)。歐文打過六年ABA聯賽，曾效力於維吉尼亞Squires和丹佛掘金隊。但他也沒能成為步行者隊的救世主。
1984-85賽季，球隊在頭兩個月的比賽中3勝21負，其中的12連敗平了球隊歷史紀錄，最後的戰績是22勝60負。凱洛格(場均18.6分9.4個籃板)和威廉士(場均18.3分8.5個籃板)再次成為隊中的得分和籃板領先者。同時，速度超快的喬治亞大學新秀後衛維恩-弗萊明(Vern Fleming) 也開始成為球隊中堅。弗萊明身高6尺5寸，每場平均14.1分。儘管球隊依然墊底，但這些優秀的年輕隊員們為步行者隊後來的崛起打下了堅實的基礎。
1985-86賽季，步行者隊在NBA選秀中以首輪第二順位選中來自俄克拉荷馬大學的前鋒韋曼-提斯代爾(Wayman Tisdale)。威廉士、凱洛格、提斯代爾、弗萊明和斯蒂潘諾維奇都是出色的球員，但是26勝56負的戰績證明他們還不夠出色。
1986-87賽季傑克-拉姆塞(Jack Ramsay)接過了步行者隊的教鞭，在此之前他在波特蘭有十年的執教經驗。拉姆塞如有神助，幫助步行者隊完成了戲劇性的大逆轉，自1981年以來首次殺入季後賽。球隊開局不錯，6勝4負，整個賽季始終保持著旺盛的鬥志。賽季收官時的表現更加出色，最後16戰10勝。步行者隊在季後賽首輪遇到了亞特蘭大老鷹隊，在兩連敗之後以96-87迎來了他們加盟NBA之後的首場季後賽勝利。之後他們輸掉了下一場比賽，以1比3的總比分被淘汰。
1987-2005：米勒時代
1987-88 米勒君臨
菜鳥米勒1987-88賽季綽號“火槍手”的新秀查克-珀森(Chuck “the rifleman” Person)以及約翰-朗(John Long)成為隊中的得分王。朗此前在底特律活塞隊效力了八年。珀森身高6尺8寸，體重225磅，畢業於奧本大學。他砍下了全隊最高的場均18.8分，並當選為NBA當年最佳新秀。威廉士、提斯代爾、弗萊明和斯蒂潘諾維奇得分全部上雙。在1987年的NBA選秀中，步行者隊在首輪第11順位挑中了得分機器、畢業於加州大學洛杉磯分校(UCLA)6尺7寸的後衛雷吉-米勒(Reggie Miller)。米勒出身於運動員世家：姐姐謝莉爾(Cheryl)曾經叱吒大學女籃，並且是1984年奧運冠軍美國女籃的主力；哥哥達雷爾(Darrell)曾是棒球大聯盟(MLB)的捕手。雷吉-米勒靠著他神準的射術和不屈不撓的鬥士之魂，很快就成長為聯盟中最具威脅的得分手。
1987-88賽季步行者38勝44負，再度被摒棄於季後賽大門之外。米勒作為朗的替補只是偶爾登場，但仍然每場得到10.0分，這樣出色的表現使得他受到更多的器重。珀森場均17.0分連續第二年成為球隊的得分王，提斯代爾以場均16.1分緊隨其後。
1988-89 “飛翔的荷蘭人”
1988年NBA選秀印第安納在第二順位挑中了後來在中鋒位置挑大樑的荷蘭人里克-施密茨(Rik Smits)。 施密茨綽號“荷蘭爆扣男”(The Dunking Dutchman)，身高7尺4寸，成為步行者隊中最難對付的進攻樞紐。
1988-89賽季步行者隊經歷了一個災難般的開局——七連敗。主教練傑克-拉姆塞被迫下台，這位名人堂教頭在21年的執教生涯當中共取得了864場勝利。前球星梅爾-丹尼爾斯和喬治-歐文被抓了壯丁臨時執掌教鞭，直到步行者隊找到了拉姆塞的正式繼任者：迪克-范思哲(Dick Versace)。當一切終於安頓下來的時候，步行者的戰績已經滑落到6勝23負。他們再也沒能恢復了元氣。
2月份步行者隊進行了兩項人員調整。首先用韋曼-提斯代爾和一個選秀權從薩克拉門托國王隊換來了拉塞爾-湯普森(LaSalle Thompson)和蘭迪-維特曼(Randy Wittman)。然後又用赫伯-威廉士從達拉斯小牛隊換來了德國人德特雷夫-施拉姆夫(Detlef Schrempf)和一個二輪選秀權。步行者本賽季的戰績是28勝54負，七年中第六次在中部賽區墊底。
1月23號威廉士在與丹佛的比賽中攬下29個籃板，創造了自喬治-麥金尼斯時代之後步行者隊的單場籃板紀錄。來自荷蘭埃因霍溫的“荷蘭爆扣男”施密茨貢獻了場均11.7分、6.1個籃板，蓋帽列全聯盟第十位，併入選NBA新秀一隊。
1989-90 米勒入選全明星
1989-90賽季步行者開局頗順，19勝9負，整個賽季的成績是42勝40負。雷吉-米勒的場均24.6分是自比利-奈特1976-77賽季的場均26.6分之後俱樂部的最高得分紀錄。米勒也因此成為了步行者隊加入NBA十三年以來首位入選全明星賽事的球員。他整個賽季投中了150個三分球，一舉打破了由比利-凱勒(Billy Keller)在1975-76賽季創下的單季123個三分球的球隊歷史紀錄。
查克-珀森每場砍下19.7分，施拉姆夫也貢獻了16.2分。德國人施拉姆夫大器晚成，十多歲才開始學習籃球，大學時效力於華盛頓大學校隊。在1985-86賽季加盟達拉斯之後的三年多時間裡，施拉姆夫的表現很平庸。直到轉會印第安納之後，他才開始大放異彩。作為一個6尺10寸的前鋒，施拉姆夫嫻熟的運球和傳接球技術是在這樣高大的球員當中所不多見的。1990年季後賽，步行者首輪不幸地遇到了衛冕冠軍底特律活塞隊。活塞隊連勝三場乾脆利落地將印第安納淘汰出局。
1990-92 不是冤家不聚頭——凱爾特人兩次終結步行者
施拉姆夫1990-91賽季開戰25輪過後，鮑勃-希爾(Bob Hill)頂替了迪克-范思哲，開始執掌步行者帥印。換手如換刀：步行者隊氣象一新，在最後四個月中30勝23負，最終總成績41勝41負。米勒罰籃命中率再創新高，以91.8%的準確率刷新了球隊紀錄。施拉姆夫作為替補貢獻了場均16.1分、8.0個籃板和3.7次助攻，當選為NBA最佳第六人。米勒(場均22.6分)、珀森(場均18.4分)和施拉姆夫三人得分冠全隊。在11月23號對休斯敦火箭的比賽中，維恩-弗萊明送出18次助攻，這是步行者加盟NBA以後的單場助攻紀錄。
步行者隊季後賽首輪與波士頓凱爾特人隊苦戰五局。步行者隊中的前鋒珀森在比賽中極盡挖苦嘲弄對手之能事，儘管有狂妄自大之嫌，但是他平均每場砍下26.0分，包括三分球31投17中，也不能不讓人心存敬意。另兩位球星米勒和施拉姆夫也分別貢獻了場均22.6分和15.8分。但這並不足以壓倒凱爾特人隊。在決定命運的第五場比賽中，步行者121-124以三分之差惜敗，止步季後賽首輪。
1991-92賽季步行者隊常規賽40勝42負。四年級球員麥可-威廉士(Michael Williams)擔任球隊首發控衛，送出場均8.2次助攻，這也是自1976-77賽季唐-布斯場均8.5次助攻之後步行者隊的最高紀錄。施拉姆夫(場均17.3分、9.6個籃板、3.9次助攻)連續第二次當選NBA最佳第六人。正所謂不是冤家不聚頭，季後賽首輪步行者隊再次遇到了波士頓凱爾特人隊。可惜這次步行者隊徹底啞火，三連敗被凱爾特人橫掃。步行者隊復仇的願望再次落空。
1992-93 印第安納換走名將珀森
1992-93賽季開始之前印第安納再次對陣容進行了調整。傳奇明星查克-珀森(Chuck Person)和威廉士一起被送到明尼蘇達森林狼隊，換來了控衛普-理察森(pooh Richardson)和前鋒薩姆-米切爾(Sam Mitchell)。但這沒有對球隊有很大的影響，球隊成績一如既往地中庸，41勝41負。二年級前鋒、6尺11寸的戴爾-戴維斯(Dale Davis)56.8%的投籃命中率創下球隊新高。同時他也摘下了全隊最高的291個進攻籃板。
千年板凳、全能的施拉姆夫在他為步行者效力的最後一年裡，終於進入了球隊的首發陣容，同時也是職業生涯第一次入選全明星。整個賽季施拉姆夫砍下場均19.1分和9.5個籃板。他的單季780個籃板也創下了步行者隊的紀錄。另外值得一提的是施拉姆夫在12月8號對金州勇士隊的比賽中，22次罰籃中的，也刷新了步行者隊進入NBA以來的歷史紀錄。
步行者隊有史以來最出色的三分王雷吉-米勒本賽季投中167個三分球，和菲尼克斯的丹-馬爾利(Dan Majerle)並列榜首。這個成績比NBA的單季最高紀錄也只差5球。在4月18號對密爾沃基雄鹿隊的比賽中，他扔中八個三分球，創下新的球隊紀錄。在11月28號對夏洛特黃蜂隊的比賽中，他單場狂砍57分。這是步行者隊加盟NBA以來的最高單場得分紀錄，比ABA聯賽時期喬治-麥金尼斯在1972-73賽季創下的球隊史上最好成績也只差一分。到1992-93賽季末，米勒職業生涯已經砍下9305分，成為步行者隊NBA時期的總得分王，即使算上ABA時期的球員在內，這個成績也能排在第四位。而米勒的職業生涯才剛剛過了三分之一……
步行者隊重返季後賽，但再次止步於首輪。這次他們總比分1比3負於紐約尼克斯隊。里克-施密茨在此輪季後賽中表現生猛，場均拿到22.5分。而米勒更是神勇，每場平均砍下驚人的31.5分。因為屢次季後賽表現不佳，本賽季之後印第安納解僱了鮑勃-希爾，任命名教頭拉里-布朗(Larry Brown)為主帥。儘管布朗打一槍換一個地方的方式一直以來為人詬病，但是在他執教大學聯賽、ABA和NBA的所有21個賽季中，20次勝率超過50%，這樣輝煌的成績是誰也無法否認的。挖來布朗的是當時步行者隊的俱樂部主席唐尼-沃爾什(Donnie Walsh)，他是布朗在北卡大學時的隊友，兩人有著很深的淵源。
1993-94 塞翁失馬？
名帥拉里-布朗拉里-布朗的神奇在印地安納得到延續：1994年季後賽步行者隊離NBA總決賽只差一步。然而本賽季之初球迷們還是憂心忡忡，因為賽季開始之前步行者隊用全明星前鋒德特雷夫-施拉姆夫從西雅圖超音速隊換來了德里克-麥基(Derrick McKey)。球隊總經理唐尼-沃爾什的批評者們罵聲四起。印第一家報紙的標題這樣寫道：“沃爾什終於組建了一支強隊……然而，是為西雅圖建的。”
這個賽季絕大多數時間步行者隊和以往沒有什麼兩樣，戰績平平，勝率一直保持在50%上下。但是到了四月份季後賽臨近的時候，步行者隊突然爆發。最後八場比賽他們獲得全勝，常規賽最後戰績47勝35負。進入季後賽，步行者隊依然炙手可熱，首輪橫掃奧蘭多魔術隊，東區半決賽出人意料地以總比分4比2淘汰了常規賽排名第一的亞特蘭大老鷹隊。
仿佛一夜之間，步行者隊就變成了一支攻守平衡內外兼顧的強隊：里克-施密茨內線得分穩定，雷吉-米勒外圍遠投神準；戴爾-戴維斯和新丁安東尼奧-戴維斯(Antonio Davis)搶籃板如拾草芥；麥基則是個萬金油。後場兩位新援——老將拜倫-斯科特(Byron Scott)和控衛海伍德-沃克曼(Haywoode workman)也起到了關鍵作用。
步行者在東區決賽中遇到了紐約尼克斯隊。尼克斯先贏下了兩個主場，但步行者回到主場後在市場廣場球館將總比分扳平。第5場決賽在紐約麥迪遜廣場花園球館(Madison Square Garden)，米勒第四節單槍匹馬一人獨得25分，帶領步行者隊取得了一場關鍵的客場勝利，將尼克斯隊逼到了懸崖邊緣。但是紐約背水一戰，頑強地贏下了後面兩場比賽，最後總比分4比3贏得東區總冠軍。儘管未能進入總決賽，但米勒在季後賽中的神勇表現一舉奠定了他NBA超級明星的地位。本賽季之後他入選夢二隊，成為隊中的得分王，並率領夢二隊贏得了1994年世錦賽冠軍。
如果說本賽季步行者隊的陣容還有缺陷的話，那就是在控衛位置。所以賽季一結束，步行者隊馬上從洛杉磯快船隊換來了前全明星球員馬克-傑克遜(Mark Jackson)。
1994-95 換湯沒換藥
巔峰期的施密茨1994-95賽季，儘管引入馬克-傑克遜加強了控衛位置，但是步行者隊還是遭遇了和上個賽季相同的命運：在東區總決賽第7場決勝局比賽中負於對手，再次與東區總冠軍失之交臂。唯一不同的是，去年的對手是紐約尼克斯隊，今年則是奧蘭多魔術隊。但這個賽季總的來說還是相當成功的。步行者隊自加盟NBA以來首次奪得分賽區冠軍，並首次在常規賽贏得50場以上的勝利(52勝30負)。上一次他們取得這樣的成績還是在遙遠的1972-73賽季，當時步行者隊在ABA聯賽中51勝33負，並最終奪得ABA聯盟總冠軍。
里克-施密茨打了他NBA最出色的一個賽季，場均17.9分7.7個籃板，都是職業生涯最高的。得分王米勒續寫著他的傳奇：場均19.6分，罰籃命中率89.7%排名全聯盟第四，三分球命中率41.5%排名第十五，1995年全明星首發，併入選NBA最佳陣容三隊。在東區半決賽對老冤家紐約尼克斯隊的比賽中，第一場比賽在客場麥迪遜花園廣場，米勒演繹了至今仍為球迷津津樂道的經典的米勒時刻：最後16.4秒神奇米勒連得8分，在落後尼克斯6分的情況下，不可思議地完成了大逆轉並贏得比賽勝利。步行者隊進而苦戰七場淘汰了尼克斯隊。
德里克-麥基在隊中所起的關鍵作用也絕不應當被忽視：搶斷列隊中第一，助攻第二，籃板和得分同為第三。作為聯盟最好的防守球員之一，麥基在賽季末入選NBA的最佳防守陣容第二隊。
1995-96 步行者的不幸——米勒受傷
1995-96賽季步行者隊的命運同全明星米勒緊緊聯繫在一起。不幸的是，米勒在4月13日的比賽中與對手撞在一起，眼角骨骨折。主心骨因傷缺陣，步行者季後賽首輪就被亞特蘭大老鷹隊淘汰。
在米勒受傷之前，他和步行者隊所向披靡，贏得了前十場比賽中的八場，常規賽戰績52勝30負。季後賽對亞特蘭大老鷹隊，在米勒缺席的頭四場比賽中步行者隊和對手戰成2比2平。關鍵的第5場決勝局在步行者隊主場市場廣場球館進行。儘管米勒神奇復出，並獨得29分，但步行者隊仍然以2分惜敗，止步季後賽。
季後賽的提前出局使得球隊出色的常規賽表現成了竹籃打水一場空。這是球隊建隊以來的第二個50勝賽季，也是第二次連續兩個賽季獲勝50場以上。也許最能體現他們本賽季水平的是：步行者隊是唯一一支在常規賽季中兩次擊敗當時如日中天的芝加哥公牛(72勝10負)的球隊。
米勒本賽季的場均21.1分體現了他的全明星價值。步行者隊前場星光閃耀，包括中鋒里克-施密茨(場均18.5分)、前鋒德里克-麥基(最佳防守陣容二隊)和戴爾-戴維斯(全隊最高的9.1個籃板)。本賽季之後，米勒和兩個戴維斯(戴爾和安東尼奧)的續約使得球迷有理由相信，步行者隊下個賽季殺入季後賽指日可待。可事實呢？
1996-97 無緣季後賽
季後賽的常客步行者隊在1996-97賽季卻出人意料地被摒棄在季後賽大門之外。在連續七年殺入季後賽之後，本賽季步行者隊39勝43負，徹底無緣季後賽。
整個賽季步行者隊都徘徊在勝率50%的邊緣。儘管球隊基本保持了94-95賽季殺進東區決賽的原班人馬，儘管球隊要風格有風格(得分王米勒場均21.6分)、要力量有力量(戴維斯二人組合力每場摘下17.0個籃板)，但是他們始終只差一口氣，未能奪得一個季後賽席位。
腳傷長期困擾著步行者隊五分之二的首發陣容：里克-施密茨因腳部手術缺勤30場；前鋒德里克-麥基左腳骨折，好不容易在4月份復出，僅過了一個星期又不幸地跟腱撕裂。步行者隊在賽季中從丹佛掘金隊重新召回了94-95賽季的功臣馬克-傑克遜。傑克遜平均每場送出11.4次助攻，超過了約翰-斯托克頓(John Stockton，此前連續9年的助攻王)成為NBA新的助攻王。但是他的傑出表現並不足以幫助球隊進入季後賽，步行者隊以一個三連敗為本賽季劃上了句號。
主帥拉里-布朗將球隊的失敗歸咎於自己頭上，認為自己沒能充分挖掘隊員的潛力。這位在1月7日剛剛贏得他NBA執教生涯第600場勝利的功勳教頭，在本賽季後辭職。在布朗執教的四年當中，步行者隊曾經兩次與總決賽失之交臂。接過步行者隊帥印的是另外一個拉里——NBA傳奇人物、印第安納本地人大鳥拉里-伯德(Larry Bird)。
1997-98 大鳥軍展翅
1997-98是印第安納球迷們充滿期待的一個賽季，最主要的原因就是因為印第安納土生土長的大鳥伯德接過了教鞭。作為NBA歷史上最出色的球星之一，大鳥很快就證明他同樣有著當主教練的天賦。他率領步行者隊取得常規賽58勝24負的球隊歷史最好成績，並再次離NBA總決賽只有一場勝利之遙。
大鳥軍基本保留了拉里-布朗的全部班底，只做了一項大的變動—引進了大鳥在1992年夢之隊的隊友克里斯-穆林(Chris Mullin)。穆林外圍遠投的精準是眾人皆知的，但此前沒人知道伯德在主教練的位置上到底有什麼能耐。但沒過多久，人們就發現大鳥作為球員所積累的豐富經驗實在是一筆寶貴的財富，同時他平易近人的氣質也很快地贏得了球員們的尊重。
防守方面，在經驗豐富的助理教練迪克-哈特(Dick Harter)的幫助下，步行者隊成為了聯盟中的頂尖防守強隊。球隊腳踏實地，每場比賽都兢兢業業，正如伯德打球時的風格。而進攻方面，在助理教練里克-卡萊爾(Rick Carlisle)的指導下，球隊緊緊圍繞著全明星米勒和施密茨做文章。隊中得分王米勒每場平均拿下19.5分，併入選NBA最佳陣容(All-NBA)三隊。 施密茨(場均16.7分、6.9個籃板、1.21次蓋帽)首次入選全明星陣容，並在全明星賽上貢獻了10分7板4助攻。
除了米勒和施密茨的優異表現之外，步行者隊的其他隊員也十分搶眼。隊中的籃板王戴爾-戴維斯場均8.0分7.8個籃板；安東尼奧-戴維斯貢獻了9.6分和6.8個籃板；搶斷王穆林場均1.16次搶斷11.3分；馬克-傑克遜場均8.7次助攻列全聯盟第三，他在對老東家紐約尼克斯的東區半決賽中表現尤為槍眼：拿下了步行者隊歷史上的首個季後賽三雙—22分和全場最高的14個籃板、13次助攻，幫助球隊以99-88戰勝了尼克斯隊。
在接連淘汰了騎士隊和尼克斯隊之後，步行者隊與芝加哥公牛隊的東區總決賽萬眾矚目。在常規賽季中，因為步行者與二連冠的衛冕冠軍公牛隊之間四場比賽平分秋色，這給了球隊很強的信心。
神奇的米勒時刻步行者隊先是輸掉了兩個客場。接下來主場在陣亡將士紀念日(Memorial Day)這個長周末，給市場廣場球館的觀眾們奉獻了兩場精彩的勝利。米勒在他輝煌的職業生涯篇章中添加了絢爛的一筆：決賽第3場，他在腳踝扭傷的情況下，最後4分半鐘拿下了自己28分中的13分，為球隊107-105獲勝立下頭功；第4場，他在比賽結束前2.7秒的三分球幫助球隊以2分反超，最後96-94獲得勝利。神奇的米勒時刻！
接下來的兩場比賽雙方各勝一場，總比分戰成3比3平。決勝的第7場，步行者隊在比賽結束還剩9分鐘的時候還以72-69領先。但是他們沒能笑到最後。公牛隊關鍵時刻加大了防守力度，控制了前後場籃板，皮蓬投中兩個關鍵進球，最後公牛隊以88-83贏得東區冠軍。在隨後的NBA總決賽中，公牛隊戰勝對手贏得三連冠。
1998-99 又是尼克斯
本賽季步行者隊六年中第四次殺入東區總決賽，但再次未能染指東區冠軍，這次他們的對手是老冤家、本賽季的黑八紐約尼克斯隊。
印第安納季後賽中先後淘汰了密爾沃基和費城殺入東區決賽。在決賽中他們和常規賽排名第八的黑馬(史稱黑八)紐約尼克斯隊鏖戰六場，在決勝場的比賽中，尼克斯隊阿蘭-休斯頓(Allan Houston)一人獨得32分，以90-82淘汰了步行者隊。
本賽季由於球員工會一度號召罷工，賽程縮短。步行者隊常規賽季33勝17負。米勒再次成為隊中得分王(場均18.4分)，並且以91.5%的罰籃命中率(247罰226中)在全聯盟居首。戴爾-戴維斯破紀錄地連續第六年成為隊中籃板王(場均8.3個)。在市場廣場球館經歷了二十五年的風風雨雨之後，步行者隊將在下個賽季遷入新建成的康塞科球館(Conseco Fieldhouse)。
1999-00 新球館、新氣象
賽季之初步行者隊不是很順。球隊送走了很受歡迎的安東尼奧-戴維斯，換來了選秀第5順位的喬納森-本德(Jonathan Bender)。此舉引來一片指責聲，因為儘管本德才華橫溢，但從高中直接選入NBA的他需要一段時間的成長過程，並不能使球隊馬上獲益。包括馬克-傑克遜在內的老將們紛紛指責俱樂部主席唐尼-沃爾什不顧球隊成績的做法。在平庸的7勝7負的開局之後，似乎步行者隊本賽季唯一值得談論的只有球隊新居——康塞科球館。球隊在市場廣場球館打完季前賽之後，於1999年11月6日開始正式啟用康塞科球館。
但是球隊迅速擺正了方向，不僅完成了一個成功的賽季，而且打出了球隊加盟NBA以後最出色的一個季後賽。步行者歷史上第一次贏得東部賽區冠軍並殺入總決賽。可惜在總決賽中他們遇到的是強大的OK二人組湖人王朝。步行者隊最後總比分2比4不敵對手。值得一提的是，步行者隊在新主場取得25連勝，這是球隊的又一項歷史紀錄，並且以56勝26負的常規賽戰績連續第二年贏得中部分區(Central Division)冠軍。
總決賽對湖人在個人統計方面，小前鋒杰倫-羅斯(Jalen Rose)進入首發陣容，並獲得NBA最快進步球員獎(Most Improved Player award)。羅斯也使得步行者隊11年以來首次有人超越米勒成為隊中得分王(場均18.2分)。奧斯汀-克羅希爾(Austin Croshere)頂替了羅斯的第六人位置，為球隊貢獻良多，特別是季後賽的表現更加突出。羅斯和克羅希爾的表現彌補了戴維斯離去帶來的損失，極大地幫助了米勒、馬克-傑克遜、戴爾-戴維斯、里克-施密茨以及特拉維斯-貝斯特(Travis Best)等核心球員。
在季後賽首輪當中，步行者靠戴爾-戴維斯關鍵時刻的一個前場籃板和貝斯特的三分球，經過5場鏖戰淘汰了密爾沃基雄鹿隊。次輪他們用了六場比賽連續第二年在季後賽第二輪淘汰了費城76人隊。東部賽區決賽是上賽季歷史重現，對手又是紐約尼克斯隊。但是這次步行者隊吉星高照，成功復仇。他們前四場比賽戰成2比2平。步行者在主場贏得了第5場，接著在客場麥迪遜廣場花園靠米勒的34分擊敗對手，有史以來第一次殺入NBA總決賽。
總決賽中步行者的對手是如日中天的由OK二人組(沙奎爾-奧尼爾，Shaquille O'Nea和科比-布萊恩特，Kobe Bryant)領銜的湖人王朝。他們先輸掉了兩個客場，回到主場後以100-91贏得了球隊有史以來的第一場NBA總決賽勝利。第4場決賽，步行者隊經過加時以兩分之差惜敗，比分是120-118。儘管在第5場決賽中步行者以120-87狠狠地羞辱了湖人隊，但後者在第6場決賽中在洛杉磯主場116-111終結了步行者的總冠軍夢想。湖人奪冠後主場斯台普斯中心球館(Staples Center)外引發了球迷騷亂。
2000-01 又一位傳奇人物入主
在用基本相同的陣容拼殺了七個賽季之後，本賽季步行者隊的陣容終於有了極大的改變。主教練大鳥伯德在執教了三個異常成功的賽季之後宣布退休。中鋒里克-施密茨在訓練營開始前一個禮拜也做出了同樣的決定。克里斯-穆林提出離隊請求，他想回到金州勇士隊，他的職業生涯就是從那裡開始的。自由球員馬克-傑克遜因為一份長約去了多倫多。戴爾-戴維斯對球隊給自己的新契約表示不滿，因此被送到波特蘭換來了傑梅因-奧尼爾(Jermaine O'Neal)。而另一位NBA歷史上的傳奇人物、同樣沒有執教經驗的名人堂成員、微笑刺客伊賽亞-托馬斯(Isiah Thomas)入主印第安納，接過了大鳥伯德手中的教鞭。
微笑刺客托馬斯不出意料之外，因為有了如此多的新面孔，步行者隊本賽季前半段舉步維艱。很快人們就看出印第安納已經退出東部冠軍的競爭者行列，他們最終落到和波士頓凱爾特人隊競爭最後一個季後賽席位的尷尬境地。3月30日步行者隊客場與凱爾特人進行生死交關的季後賽席位爭奪戰，在此之前他們還落後凱爾特人一場。本場比賽步行者隊92-87取勝，並一發不可收拾，在剩下的11場比賽中取得9場勝利，其中包括一個七連勝。最後步行者隊在12個賽季中第11次殺入季後賽。
杰倫-羅斯已經逐步成長為NBA的一流球星，他本賽季拿到了職業生涯最高的場均20.5分。這也是小奧尼爾第一個完整的首發賽季，他開始向人們展現自己的真正實力：場均12.9分9.8個籃板；單季228個蓋帽在全聯盟並列首位，這也刷新了球隊的蓋帽歷史紀錄。特拉維斯-貝斯特也打出了職業生涯最出色的一個賽季：場均11.9分6.1次助攻，是全聯盟表現最出色的第六人之一。年輕隊員艾爾-哈靈頓(Al Harrington)和傑夫-福斯特(Jeff Foster)偶爾的閃光點也預示著他們光明的未來。
季後賽再次成為米勒的獨角戲。常規賽排名第八的步行者遇到了奪冠大熱門頭號種子76人隊。在第一場客場比賽中，米勒時刻再現：比賽結束前2.9秒米勒使出殺手鐧，三分中的，以1分的優勢79-78戰勝76人，爆出大冷門。米勒在後面三場比賽平均每場砍下36.0分，但終究獨木難支，三連敗被76人隊以總比分1比3淘汰。
2001-02 球隊大換血
本賽季中段步行者隊和芝加哥公牛隊完成了一樁驚人交易，使得年輕的步行者隊變得更加年輕。交易之前，步行者隊戰績不佳，26勝27負即將無緣季後賽。球隊痛定思痛，用杰倫-羅斯、特拉維斯-貝斯特和一個二輪選秀權從芝加哥公牛隊換來了布拉德-米勒(Brad Miller)、羅恩-阿泰斯特(Ron Artest)、凱文-奧利(Kevin Ollie)和羅恩-莫瑟(Ron Mercer)。
交易之後步行者取得16勝13負，包括最後5場比賽全勝，並排名第八在13年中第12次打入季後賽。 季後賽首輪的對手是頭號種子新澤西籃網隊，步行者隊頑強地與對手打滿5場，並在決勝的第5場中打了兩個加時。可惜米勒的31分(包括將比賽拖入第一次加時的一個招牌三分球)不足以使步行者隊戰勝對手。新澤西籃網隊淘汰對手並最終取得東部賽區冠軍。
在常規賽季中，米勒超越了哈爾-格里爾(Hal Greer)、大鳥伯德和克萊德-德雷克斯勒(Clyde Drexler)，在NBA總得分排行榜中上升到第18位。本賽季結束後，米勒的職業生涯總得分達到22623分。
小奧尼爾開始嶄露頭角，首次入選全明星。他平均每場拿到19.0分、10.5個籃板和2.3次蓋帽，全部都是隊中最高。他也因此獲得NBA進步最快球員稱號，併入選最佳陣容三隊。
小奧尼爾和米勒也同時入選美國代表隊，參加2002年在印第安納波利斯舉行的世錦賽。另外，在選秀日從亞特蘭大交換來的新秀控衛賈馬爾-廷斯利(Jamaal Tinsley)表現搶眼，兩次當選月度最佳新秀。最佳替補艾爾-哈靈頓因傷缺席了步行者隊賽季後半段的比賽。他在1月23日的比賽中膝蓋受傷，不得不接受手術。受傷之前，哈靈頓為球隊貢獻了每場13.1分和6.3個籃板。
2002-03 虎頭蛇尾
在取得了球隊有史以來最好的開局(13勝2負)之後，步行者因為種種原因未能將良好的勢頭保持下去。儘管最終48勝34負的常規賽成績還要好於上個賽季，但是他們還是沒能擺脫連續第三年季後賽首輪被淘汰的命運。這次他們的對手是黑馬波士頓凱爾特人隊。在全明星賽之前步行者隊的戰績(34勝15負)排在東部第一，因此主教練托馬斯和他的教練班底獲得執教東部全明星隊的殊榮。球員中小奧尼爾連續第二年入選，也是首次進入全明星首發陣容。布拉德-米勒則首次入選全明星。
在全明星賽結束後的三場聯賽中獲勝之後，步行者隊的戰績提高到37勝15負。但此後步行者判若兩隊，後30場比賽取得了蹩腳的11勝19負。箇中原因很多，包括布拉德-米勒的受傷、阿泰斯特的數次被停賽，以及小奧尼爾、廷斯利和克羅希爾各自的家庭悲劇。小奧尼爾的個人榮譽不斷。他連續第二年入選NBA最佳陣容三隊，同時被挑中代表美國隊參加2004年奧運會選拔賽。
2003-04 重回巔峰
小奧尼爾羽翼漸豐本賽季之前的一系列大動作使得球隊迎來了歷史上最為豐收的一個賽季。全明星中鋒布拉德-米勒成為自由球員，由於他的要價超出了球隊所能承受的範圍，他被送到薩克拉門托國王隊換來了斯科特-波拉德(Scot pollard)。大鳥伯德回歸，任俱樂部主席。原俱樂部主席唐尼-沃爾什成為CEO。大鳥新官上任三把火，解僱了主帥以賽亞-托馬斯，里克-卡萊爾接任。球隊主心骨小奧尼爾和雷吉-米勒相繼續約，保證了球隊主力陣容的穩定性。這一系列的調整並不影響步行者隊在常規賽季勢如破竹，取得61勝21負的NBA最好成績，也創下了球隊歷史上的勝率新紀錄。小奧尼爾星光閃耀，第三次成為全明星，併入選NBA最佳陣容二隊。羅恩-阿泰斯特脫胎換骨，首次入選全明星，並榮獲NBA年度最佳防守隊員獎項(DPOY)。卡萊爾則成為繼帕特-萊利(Pat Riley)之後第一位在執教的頭三個賽季每次都贏得分賽區冠軍的教練。
季後賽首輪步行者隊橫掃波士頓，報了上賽季被對手淘汰的一箭之仇。接著總比分4比2 淘汰勁旅邁阿密熱隊，11年中第6次殺入東部賽區總決賽。在決賽中他們總比分2比4不敵底特律活塞，後者繼而在總決賽中橫掃湖人，奪得NBA總冠軍。
2004-05 再見，米勒大叔！
正當全隊上下躊躇滿志地準備奪取歷史上第一個NBA總冠軍之時，一場突如其來的災難沉重地打擊了步行者隊，那就是臭名昭著的“奧本山宮殿群毆事件”。2004年11月19日，在底特律奧本山宮殿球館，因為羅恩-阿泰斯特和一個現場球迷的衝動，本來是步行者隊和活塞隊的兩強相爭，演變成為兩隊隊員和現場球迷之間的互毆。一時之間拳腳與板凳齊飛、球迷與隊員共“武”。因為這場騷亂的惡劣影響，步行者隊遭到了史無前例的嚴重處罰。阿泰斯特遭禁賽整個賽季(包括季後賽)，史蒂芬-傑克遜(Stephen Jackson)禁賽30場，小奧尼爾禁賽25場(後來減為15場)。三大主力遭禁，剩下的隊員並未氣餒。他們同仇敵愾，在雷吉-米勒的率領下為這位39歲的傳奇人物的最後一個賽季劃上了完美的句號。
主力陣容的殘缺不齊讓主教練里克-卡萊爾絞盡腦汁。他至少試過17名首發隊員，30種不同的陣容組合。球隊不僅受到禁賽的沉重打擊，多名關鍵球員也因傷缺陣多場，包括小奧尼爾(肩傷)、賈馬爾-廷斯利(腳傷)、傑夫-福斯特(臀部手術)。而米勒因在季前賽中左手手骨骨折，賽季初一直坐在傷病席上。
在小奧尼爾缺席的場次中，米勒獨臂擎天，6次獨得30分以上，平均每場得分20分。全隊眾志成城，不僅奇蹟般地殺入季後賽，而且排名東區第六。在季後賽首輪，步行者隊爆冷以總比分4比3淘汰了大西洋賽區冠軍波士頓凱爾特人隊。在東區半決賽中，2比4不敵衛冕冠軍底特律活塞隊，其中米勒在他的告別賽——半決賽第6場中獨得27分。此戰過後，米勒將告別他征戰了18個賽季的NBA舞台。他的職業生涯總得分25267分，在NBA總分排行榜上名列第12位。在他為步行者隊效力的18年間，球隊15次打入季後賽。
2005-2010：後米勒時代
2005-06 延續紀錄
開季時候的高期待值很快就被打破，阿泰斯特令人震驚地提出交易請求，再次在一個良好的開局後破壞了球隊。隨後傷病成為頭號影響因素，迫使卡萊爾使用了31套不同的首發陣容，包括了14名球員。事實上，開季時候預期的先發陣容(廷斯利、傑克遜、阿泰斯特、奧尼爾和福斯特)從沒有共同上陣過。奧尼爾缺陣31場，大部分時候是因為腹股溝傷勢。廷斯利，受困於腳部和踝關節傷勢，錯過了40場比賽。即便有這些困難，步行者依然設法保持了兩項紀錄未被打破：他們連續9年勝率不低於5成且殺入季後賽，後一項紀錄和聖安東尼奧馬刺並列，是當時聯盟仍在延續的最長的連續季後賽紀錄。
也有一些個人的閃光點，首輪選中的丹尼-格蘭傑(Danny Granger)打出漂亮的新秀賽季，展示了他籃球智慧的閃光。老將安東尼-詹森(Anthony Johnson)頂替廷斯利，打出了生涯最好的一個賽季。用阿泰斯特從薩克拉門托換來的佩賈-斯托亞科維奇(Peja Stojakovic)在加盟步行者後場均接近20分。小奧尼爾成為歷史上首位在季後賽比賽中單場拿下至少35分、15籃板且投籃命中率不低於80%的球員(當場數據：35分17籃板，15投12中)，他是在首輪對陣籃網的第三場比賽做到的。詹森此後在第六場拿下了生涯最高的40分，但這也無法阻止步行者被淘汰出局。
2006-07 40年大慶的喜劇和悲劇
在斯托亞科維奇選擇和紐奧良黃蜂簽約後，步行者從亞特蘭大迎回了在當地很受歡迎的前鋒艾爾-哈靈頓，在這個繁忙的休賽期，他們還通過兩筆交易從達拉斯得到了馬奎斯-丹尼爾斯(Marquis Daniels)以及達雷爾-阿姆斯特朗(Darrell Armstrong)，將奧斯汀-克羅希爾和安東尼-詹森送去了小牛。因為頻繁交易，球隊的化學反應始終未能像希望的那樣建立起來。
隨著球隊在賽季中期依然掙扎，球隊與金州勇士之間做出大交易，得到了邁克-鄧利維(Mike Dunleavy)、特羅伊-墨菲(Troy Murphy)、埃克-迪奧古(Ike Diogu)和凱斯-麥克勞德(Keith McLeod)，將哈靈頓、史蒂芬-傑克遜、薩魯納斯-賈西科維休斯(Sarunas Jasikevicius)和約什-鮑威爾(Josh Powell)送去勇士。這筆交易最初給了步行者以幫助，不過傷病再次讓他們付出代價，尤其是丹尼爾斯因傷缺陣，讓球隊實力下滑，在全明星後遭遇11連敗。這波連敗讓步行者失去了競爭力，10年來他們第一次無緣季後賽。
2007-08 轉變的賽季
格蘭傑成為新領袖聘請了以吉姆-奧布萊恩為首的新教練組之後，球隊希望能夠重返季後賽，但他們的希望被一個老問題破壞了——具體地說，就是傑梅因-奧尼爾和賈馬爾-廷斯利的傷病。奧尼爾錯過了40場比賽，廷斯利43場，讓先發陣容沒辦法好好磨合，並導致球隊以36勝46負連續第二年無緣季後賽。
奧布萊恩則確實給球隊的打法風格打下了深刻烙印，為球隊設計了快速進攻的戰術，結果是球隊場均能拿下104分，是球隊15年以來的最高紀錄。步行者還創造了俱樂部史上三分球命中數(755)和出手數(2021)的最高紀錄，球隊有三人投中至少100個三分球(丹尼-格蘭傑、邁克-鄧利維和卡里姆-拉什)，也是隊史第一次。
球場上也有個人的成功故事，丹尼-格蘭傑和邁克-鄧利維都打出了爆發的表現。格蘭傑在他的第三年場均19.6分、6.1籃板、2.1助攻、1.19搶斷和1.05封蓋，使得自己成為球隊的新代表人物。鄧利維是聯盟最快進步獎的有力競爭者之一，在他的第六個賽季中場均貢獻19.1分、5.2籃板、3.5助攻和1.05搶斷。格蘭傑和鄧利維在三分線外都有超過40%的命中率，讓步行者擁有了一對強大的搖擺人組合作為重建基礎。
隨著賽季臨近結束，球隊CEO兼總裁唐尼-沃爾什選擇結束他在球隊漫長而成功的工作，前往紐約尼克斯擔任籃球事務總裁。步行者在沃爾什執掌下度過了前所未有的成功時代，這個時代從1986年開始，卻幾乎不因他的離去而結束。2003年回到家鄉球隊後，長期擔任沃爾什助手的拉里-伯德被認為將會主導球隊的籃球事務。
2008-09 同樣的結果，不同的感覺
在他首次成為球隊籃球事務主宰者的第一個休賽期中，伯德留下了深刻的烙印，完成了兩筆大交易(分別與多倫多和波特蘭)，為球隊帶來了老將後衛TJ-福特(TJ Ford)和加萊特-傑克(Jarrett Jack)，以及首輪新秀布蘭登-拉什(Brandon Rush，13號，來自堪薩斯大學)和羅伊-希伯特(Roy Hibbert，17號，來自喬治城大學)，將長期以來的明星，但已經走下坡路的傑梅因-奧尼爾送去了猛龍。球隊花了一些時間來找到感覺，因為他們新添了7張新面孔，最重要的復出球員邁克-鄧利維因膝傷倒下，並因此錯過了賽季大部分比賽，最終不得不接受大手術。
在11月和12月都表現掙扎之後，球隊在賽季的2009年部分實現了勝多負少(26勝25負)，但是連續第三年沒能進入季後賽。這個賽季充滿了膠著的比賽和戲劇化的最後時刻——步行者有21場比賽最終分差不超過3分，包括在最後一秒戰勝了湖人與騎士，以及大勝凱爾特人。他們還打了5場加時賽。
個人表現也有很多成績，最重要的是丹尼-格蘭傑打出了全明星級別的表現。球隊的新當家球星場均得到25.8分，是自1976-77賽季比利-奈特的26.6分以來，步行者球員單賽季的最高場均得分，也成為NBA歷史上第一位連續三年場均得分都提高至少5分的球員。特羅伊-墨菲成為NBA歷史上第一位在籃板(場均11.8個，第二)和三分命中率(45.0%，第三)上都排名聯盟前五的球員，還創下了球隊防守籃板(715個)、總籃板(861個)、場均籃板和兩雙次數(49)的新紀錄。
2009-10 失敗中摸索前進
在2009年nba選秀大會上，步行者摘下了來自北卡的前鋒泰勒-漢斯布魯(Tyler Hansbrough)和來自康大的後衛AJ-普萊斯(AJ Price)。步行者還與自由球員鄧台-瓊斯(Dahntay Jones)簽約四年，與所羅門-瓊斯(Solomon Jones)簽約兩年，與厄爾-沃特森(Earl Watson)簽約一年。三名球員被球隊相中都是因為他們的防守能力，這正是步行者過去所缺乏的(步行者在2008-09賽季失分聯盟第五高)。
步行者還完成了與賈馬爾-廷斯利(Jamaal Tinsley)的買斷契約，而自由球員加萊特-傑克(Jarrett Jack)和拉蘇-內斯特洛維奇(Rasho Nestrovic)則被猛龍簽走。
漢斯布魯在自己的新秀賽季因為耳道感染沒打幾場比賽，另外一位內線傑夫-福斯特(Jeff Foster)同樣因傷幾乎賽季報銷。步行者連續四年低於50%勝率，無緣季後賽。儘管整個賽季是令人失望的，但步行者5年來第一次在常規賽橫掃活塞，20年來第一次橫掃籃網，並在賽季尾聲階段顯示出一些上升的跡象，他們最後的14場比賽拿下了10場勝利。
2010年的選秀大會上，步行者首輪選中保羅-喬治(Paul George)、第二輪選中蘭斯-史蒂芬森(Lance Stephenson)，為球隊注入了新的活力。8月11日，球隊又完成了一筆四方交易，送出特洛伊-墨菲(Troy Murphy)，得到達倫-科里森(Darren Collison)和詹姆斯-波西(James Posey)。
