Coba jelasin Dallas Mavericks (1998–2004) dari Steve Nash dong

Di Dallas itulah Nash memantapkan dirinya sebagai point guard yang tangguh, memulai satu dekade sebagai salah satu pemain top permainan. Selama tahun pertamanya sebagai Maverick (Musim  yang diperpendek) ia memulai di semua 40 pertandingan yang ia mainkan, dan rata-rata 7,9 poin, 2,9 rebound dan 5,5 assist per game. Dengan rekor 19-31, Mavericks gagal membuat playoff 1999, tetapi di musim 1999-2000, prospek tim meningkat pesat. Nash melewatkan 25 pertandingan pertengahan musim karena cedera pergelangan kaki, tetapi kembali mencatatkan enam double-double di bulan terakhir permainan. Dia menyelesaikan musim dengan rata-rata 8,6 poin dan 4,9 assist per game. Lebih penting lagi untuk tim, rekan setim dan teman tahun kedua Dirk Nowitzki berkembang pesat menjadi pemain top, veteran Michael Finley mengalami tahun berkaliber All-Star, dan pemilik baru tim, miliarder Mark Cuban, membawa energi baru dan kegembiraan untuk tim. Nash sekarang memiliki lingkungan yang mendukung di mana dia bisa berkembang.

Pada tahun , Nash rata-rata 15,6 poin dan 7,3 assist per game di musim breakout. Dengan Nash mengarahkan serangan tim, Nowitzki dan Finley bermain dalam performa terbaik mereka, dan akuisisi All-Star Juwan Howard melengkapi trio skor tinggi, Mavericks mendapatkan tempat playoff untuk pertama kalinya dalam lebih dari satu dekade. Dallas kalah di Semifinal Wilayah Barat empat pertandingan melawan San Antonio Spurs, tetapi itu menandai awal dari perjalanan yang tak terlupakan bagi Nash dan Mavericks. Pada , Nash membukukan karir tertinggi 17,9 poin dan 7,7 assist per  dan mendapatkan tempat di NBA All-Star Game dan di All-NBA Third Team. Dia sekarang menjadi All-Star, semakin sering muncul di iklan televisi dan, dengan Finley dan Nowitzki, menjadi bagian dari "Tiga Besar" Dallas Mavericks. Dallas mendapatkan perjalanan ke babak playoff lagi tetapi kalah lagi di Semifinal dari Sacramento Kings 4-1.

Nash hampir meniru penampilan musim sebelumnya di musim , rata-rata 17,7 poin dan 7,3 assist per game, kembali mendapatkan penghargaan All-Star dan All-NBA Third Team. Nowitzki dan Nash memimpin Mavericks dari 14 kemenangan beruntun untuk membuka musim hingga ke Final Wilayah Barat, di mana mereka akhirnya kalah dari juara NBA, San Antonio Spurs 4-2. Itu hanya penampilan Final Konferensi kedua dalam sejarah waralaba.  melihat daftar Mavericks yang ditingkatkan secara ofensif (dengan akuisisi Antoine Walker dan Antawn Jamison) tetapi penurunan dalam kontribusi penilaian Nash. Akibatnya, ia tidak dipilih untuk daftar nama tim All-Star dan All-NBA meskipun ia mencapai rekor tertinggi dalam kariernya dalam assist per game (8,8) dan akurasi lemparan bebas (91,6%). Pada babak playoff 2004, unggulan kelima Dallas gagal membuat kemajuan lagi karena Sacramento Kings membuat mereka kalah dari 4-1.

Setelah musim 2003–04, Nash menjadi agen bebas . Dia berusaha untuk menegosiasikan kontrak jangka panjang dengan Cuban, yang membayar Walker, Finley, Nowitzki dan Jamison hampir $ 50 juta dalam gaji gabungan musim itu. Cuban ingin membangun waralaba di sekitar Nowitzki yang lebih muda dan tidak ingin mengambil risiko menandatangani kontrak jangka panjang dengan Nash yang berusia 30 tahun, dan menawarkan kontrak empat tahun kepada Nash senilai sekitar $9 juta per tahun, dengan tahun kelima sebagian terjamin. Phoenix Suns di sisi lain menawarkan point guard kontrak enam tahun senilai $63 juta. Nash enggan meninggalkan Dallas dan kembali ke Cuban untuk melihat apakah dia akan mencocokkan kesepakatan itu; Cuban tidak melakukannya, dan Nash menandatangani kontrak dengan Suns untuk  . Nash kemudian memenangkan dua penghargaan MVP dengan Phoenix, dan pada penampilan 14 Juni 2006 di Late Show with David Letterman, Cuban bertanya-tanya dengan keras, "...Anda tahu Steve adalah pria yang hebat dan saya sangat mencintainya, tetapi mengapa dia tidak bisa bermain seperti MVP untuk kami?"