Sulus erstes Schiff als [[Captain]] ist die [[USS Excelsior|USS ''Excelsior'' (NCC-2000)]]. Bei seiner ersten Mission mit diesem Schiff soll er gasförmige Anomalien im [[Beta -Quadrant]]en kartographieren. Während dieser Mission zeichnen die Sensoren der Excelsior auch die Explosion des klingonischen Mondes [[Praxis]] auf. Sulu bietet den [[Klingone]]n seine Hilfe an, diese lehnen jedoch ab. Später hilft er [[James T. Kirk|Kirk]] dabei noch rechtzeitig nach [[Khitomer]] zu kommen, um die Teilnehmer [[Konferenz von Khitomer|Konferenz]] und damit den Frieden zu retten ([[Star Trek VI: Das unentdeckte Land]]).