Jego przełożeni dość szybko zorientowali się o jego talencie militarnymMikayel Varandian, Մուրադ' Սեբաստացի ռազմիկին կեանքն եւ գործը, Hairenik, 1931, s. 96; (wersja angielska: Mikayel Varandian, Murad of Sebastia). Popularność i sympatia, jaką zaskarbił sobie Ozanian, była tak duża, że jego żołnierze zawsze zwracali się do niego po imieniu, nawet gdy w późniejszym okresie był generałem w Cesarskiej Armii RosyjskiejAntranig Chalabian, Bold and fiercely determined, Andranik Ozanian spent most of his life as a revolutionary for his fellow Armenians, Military History, lipiec 1995, s. 10..
Pierwszą misją Andranika jako lidera fedainów było porwanie i zabicie Beshara Khalila, osmańskiego żołnierza pochodzenia kurdyjskiego, a zarazem wodza plemienia Kherzeni odpowiedzialnego za pogromy Ormian i zabicie Seroba. Khalil dokonywał serii zbrodni przeciwko ludzkości, za co jednak nie został ukarany przez rząd sułtana. Gdy Khalil zabił Seroba, paradował z jego głową po miejscowościach Muş i Bitlis, co miało na celu zastraszenie lokalnej ludności ormiańskiej. Oddział Andranika stoczył bitwę z oddziałem Khalila, a po wygranej bitwie zabił go(Armenian) ԱՆԹԱՆԵՍՅԱՆ, Վահե. "Զորավար Անդրանիկ".