Στο πρώτο έτος της βασιλείας του, η Σπάρτη συγκλονίστηκε από την αποκάλυψη της συνωμοσίας του Κινάδωνα, στόχος της οποίας ήταν η ανατροπή του πολιτικού και κοινωνικού καθεστώτος.<ref>{{Cite book|title=Ξενοφώντος, Ελληνικά Βιβλίο Γ΄|first=|last=|publisher=|isbn=|year=|location=|page=|quote=}}</ref> Λίγο αργότερα το 396 π.X. οι Σπαρτιάτες πληροφορήθηκαν, ότι οι Πέρσες επιδίδονται σε μεγάλες ναυτικές προετοιμασίες και αποφάσισαν να στείλουν τον Αγησίλαο με ένα εκστρατευτικό σώμα στη Μικρά Ασία με σκοπό την υποστήριξη και απελευθέρωση των ελληνικών πόλεων της Ιωνίας. Το σώμα αυτό αποτελούνταν από 30 Σπαρτιάτες, 2000 νεοδαμώδεις και 6000 συμμάχους στρατιώτες. Θέλοντας να δώσει πανελλήνια χροιά στην εκστρατεία του, ο Αγησίλαος ήρθε στην Αυλίδα και θυσίασε στην Άρτεμη μιμούμενος τον Αγαμέμνονα. Η ευσεβήςποκιτική αυτή πράξη αμαυρώθηκεαποκρούστηκε ωστόσο από τη συμπεριφορά τωντους ΒοιωταρχώνΒοιωτάρχες, οι οποίοι τον πρόσταξαν να μην πραγματοποιήσει τη θυσία και πέταξαν τα θυσιαζόμενα σφάγια από το βωμό<ref>{{Cite book|title=Ξενοφώντος Ελληνικά Βιβλίο Γ΄.|first=|last=|publisher=|isbn=|year=|location=|page=|quote=}}</ref>. Το 396 π.Χ. έφθασε στην [[Έφεσος|Έφεσο]] και εκεί τον συνάντησαν απεσταλμένοι του σατράπη Τισσαφέρνη θέλοντας να εξακριβώσουν το σκοπό της άφιξης του. Ο Αγησίλαος απάντησε "''για να γίνουν ανεξάρτητες οι πόλεις της Ασίας όπως είναι και στην υπόλοιπη Ελλάδα''"<ref>{{Cite book|title=Ξενοφώντος, Ελληνικά Βιβλίο Γ΄.|first=|last=|publisher=|isbn=|year=|location=|page=|quote=}}</ref> . Ο Τισσαφέρνης του πρότεινε τρίμηνη ανακωχή με σκοπό να ενημερώσει τον Μεγάλο Βασιλιά και ο Αγησίλαος αποδέχτηκε την πρόταση του. Ωστόσο καθ' όλη τη διάρκεια της ανακωχής ο Πέρσης σατράπης ζητούσε ενισχύσεις παραβιάζοντας ουσιαστικά την ανακωχή και απαίτησε από τον Αγησίλαο - όταν ισχυροποίησε τη θέση του - να εγκαταλείψει τη Μικρά Ασία. Ο Σπαρτιάτης βασιλιάς, αφού ενίσχυσε το στράτευμα του, ξεκίνησε την προέλαση του προς την Ελλησποντιακή Φρυγία. Κυριεύοντας όσες πόλεις συναντούσε στο δρόμο του, συγκεντρωσεσυγκέντρωσε πάρα πολλά λάφυρα και έφτασε στο Δασκύλειο, την έδρα του σατράπη Φαρνάβαζου Β΄. Στην ιππομαχία που ακολούθησε οι Έλληνες είχαν μικρές απώλειες και μόνο με την παρέμβαση του ίδιου του Αγησιλάου, οι δυνάμεις των Περσών υποχώρησαν. Ωστόσο ο Έλληνας ηγεμόνας συνειδητοποίησε, ότι για να έχει ελπίδες επιτυχίας έπρεπε να αναπληρώσει την έλλειψη ισχυρού ιππικού. Γι αυτό υποχώρησε προς τα παράλια και ξεκίνησε την συγκρότηση ιππικού με τη συνεισφορά των πλουσίων κατοίκων των Ιωνικών πόλεων. Για να τονώσει το ηθικό των ανδρών του καθιέρωσε βραβεία και έπαθλα για τα στρατιωτικά σώματα που θα διακρίνονταν στην στρατιωτική εκπαίδευση και έδωσε εντολή να πουλούν τους αντίπαλους αιχμαλώτους γυμνούς για να φαίνονται τα αγύμναστα κορμιά τους.<ref>{{Cite book|title=Ξενοφώντος, Ελληνικά Βιβλίο Γ΄.|first=|last=|publisher=|isbn=|year=|location=|page=|quote=}}</ref> Την άνοιξη-καλοκαίρι του 395 π.Χ. ο Αγησίλαος προέλασε προς τις Σάρδεις. Εκεί κοντά στην πόλη έδωσε μάχη εναντίον των δυνάμεων του Τισσαφέρνους και κατήγαγε περιφανή νίκη, αποκομίζοντας πάμπολλα λάφυρα. Η ήττα μοιραία έφερε και την πτώση του σατράπη. Ο Πέρσης Βασιλιάς τον θεώρησε υπεύθυνο για την αποτυχία και έστειλε τον Τιθραύστη με εντολή να αποκεφαλίσει και να αντικαταστήσει τον Τισσαφέρνη. Ο νέος σατράπης αξίωσε από τον Αγησίλαο να εγκαταλείψει τα εδάφη του βασιλιά με την υπόσχεση οι ελληνικές πόλεις να είναι μεν αυτόνομες αλλά να συνεχίσουν την καταβολή φόρου στους Πέρσες. Ο Αγησίλαος απάντησε ότι έπρεπε να πάρει τη συγκατάθεση της πατρίδας του για να δώσει την τελική του απάντηση και ο Τιθράυστης αφού του έδωσε τριάντα τάλαντα για τη συντήρηση του στρατού, τον έπεισε να αποχωρήσει στη Φρυγία ( που ήταν η περιοχή του Φαρνάβαζου Β΄), μέχρι να έρθουν εντολές από τη Σπάρτη.<ref>{{Cite book|title=Ξενοφώντος, Ελληνικά Βιβλίο Γ΄.|first=|last=|publisher=|isbn=|year=|location=|page=|quote=}}</ref>
