En 483, Zénon décide de se débarrasser de son magister militum pour l'Orient Illus et le remplace par Jean. En réaction, Illus se révolte et proclame le civil Léontius comme empereur. Jean, aidé de Théodoric qui met ses forces au service de Zénon, rassemble une grande armée et vainc les rebelles près d'Antioche en . Illus et Léontius fuient en Isaurie et s'emparent de la forteresse de Papurius, rapidement assiégée par Jean. Ce dernier capture aussi Trocundus, le frère d'Illus, vers la fin de l'année et l'exécute[1]. Le siège n'en dure pas moins jusqu'en 488 quand une trahison permet à Jean de s'en emparer et d'exécuter Illus et Léontius.
Sous Anastase, Jean est rapidement mobilisé lors de la guerre d'Isaurie[2]. En effet, le nouvel empereur souhaite mettre fin à la forte influence des Isauriens sur les destinées impériales, incarnées par Zénon, lui-même issu de ce peuple. Jean le Scythe est appuyé par Jean le Bossu et ils remportent une importante victoire à Cotyaeum en 492, qui oblige les rebelles à se réfugier au cœur de l'Isaurie, d'où ils mènent une forme de guérilla. Celle-ci dure jusqu'en 497, quand les deux généraux impériaux tuent Longinus de Cardala et Athénodorus, deux chefs rebelles, dont les têtes sont envoyées à Constantinople.
Anastase célèbre cette victoire en honorant ses deux généraux. Jean le Scythe est nommé au consulat en 498, suivi de Jean le Bossu en 499[2].
