According to Mahmud al-Kashgari, they were mentioned at Divânu Lügati't-Türk:
"Twenty twos call them "Kal aç" in Turkish. This means "Stay hungry". Later, they were called "Xalac". Their origins are these."
"Oguzs and Kipchaks translate "x" to k". They are a group of "Xalac"s. They say "xızım", whereas Turks say "kızım" (my daughter). And again other Turks say "kande erdinğ", whereas they say "xanda erdinğ", this means "where were you ?" 
According to Zemarcos' Syriac chronicle, Khalajes would be remnants of Hephthalites, were separate Turkic people. He was ambassador of Byzantine Empire to Western Gokturk Khanate in 568. According to Al Khwarizmi, was Samanid officer, they were considered as descendants of Hepthtalithes along with Kanjina Turks. Ibn Khordadbeh mentioned Khalajes lived beyond Syr Darya of the Talas region in his book Kitāb al-Masālik w’al- Mamālik with Karluks. But the information comes into contradictions that make it unreliable. The similarity between Khalaj and Karluk is difficult to determine the truth.
They ruled Zabulistan as vassals of Tahirids with title of Zunbil. They were subjugated by Ya'qub-i Laith Saffari, was founder of Saffarids in 879. According to Saffarid sources they were inhabitants of Zabulistan, this meant they lived in present Afghanistan and among Ghazni and Zamindawar. Later, they were successively ruled by Samanids and Ghaznavids.
In 1040, they revolted against Mas'ud I of Ghazni, was sultan of Ghaznavids. He sent a punitive expedition but he was defeated and later dethroned and executed by Mohammad Ghaznavi. During the Ghaznavid and Ghurid rules, some of Khalaj gradually become Ghilzai tribe of Afghan. Ghurid Ghiyath al-Din Mahmud came to power at Firuzkuh with support of them. Later they were subjected by Khwarezmshahs in 1210s. During the Mongol invasion of 1221, many Khalajes joined the Mongols but others continued to Sayf al-Din Ighrak, who formed an ephemeral independent state in the valley of Kabul. Many Khalajes then went to India and served the sultans of Delhi, in western India and even in Bengal, its members were called Khilji and founded a dynasty which ruled Delhi sultanate from 1290 to 1320 and other dynasties in various places as Malwa. Despite their Turkic origins, they were considered as Afghans for Indians.
Some of the Khalaj remained in Afghanistan, in the fourteenth century are discussed in Khalaj Abiward in northern Khorasan, they should set the thirteenth century during the struggles between Ghurids and Khwarezmhsahs. An Uzbek tribe identified by the Russians in the 19th century with the name of Galachi, would originate from Khalaj. Other groups are indicated in Kerman and Fars as well as in Azerbaijan and Anatolia. A region of western Persia, the mountainous region southwest of Tehran towards Hamadan named traditional Khalajistan, especially living in the districts (shahristans) of Sawa and Arak Province (ustan) of Markazi, and in territories inhabited by Bakhtiyaris including some close to the central mountains of Zagros.
The origin of the Khalaj is a rather obscure subject and still remain controversial. According the Encyclopaedia Iranica:
The origin of the Khalaj is controversial. Arab geographers mentioned them already in the 9th and 10th centuries, and the Khalaj were listed among the Turkic people of the steppes of Central Asia. It is difficult to identify whether the Khalaj mentioned in those accounts are identical with the present people of the same name. Sometimes they were also considered as descendants of the Hephthalites, or as those of turkisized Iranians, or precisely as the Sakas (cf. Bosworth and Clauson, pp. 8 ff.). According to the Arab geographer Ebn Ḵordāḏbeh, their earliest known settlement was located in the Talas region beyond the Syr Darya River (Bosworth, p. 917). Based on the record of another Arab geographer, Moḥammad b. Najib Bakrān, in the 13th century the Khalaj moved from the Qarluq area, where they were involved in conflicts with the GHURIDS, to Zābolestān (cf. Minorsky, 1940-42, pp. 426-34; Idem, 1937, pp. 346-48). In the course of the Mongol conquests, parts of the Khalaj migrated westwards. Moḥammad b. Najib Bakrān had already mentioned Khalaj settlements in Khorasan in the 13th century (Bosworth, p. 917). The remembrance of this former presence of the Khalaj is still kept in the form of several toponyms. In Kermān and Fārs, the presence of the Khalaj is said to date back to the late Saljuq period (end of the 12th century).
- Histoire des Turcs de l'Asie centrale, Vasily Bartold