Människor i Yilis multietniska område måste lämna proverna innan de tillåts resa utomlands.
Den kinesiska regeringen försöker slå ner på periodiskt våld, vilket den skyller på islamistiska militanter.
Många muslimer i Xinjiang säger att de diskrimineras.
De säger att de kinesiska myndigheterna ofta vägrar att utfärda dokument som tillåter dem att resa.
De flesta av den uiguriska etniska minoriteten, som utgör omkring 45 procent av Xinjiangs befolkning, utövar den muslimska tron. Under årens lopp har Kinas myndigheter tillskrivit uiguriska militanter våldsamma attacker, som de säger är inspirerade eller hjälpda av utländska terrorgrupper.
Uigurledare har förnekat att de ligger bakom våldet.
Varför finns det spänningar mellan Kina och uigurerna?
Fungerade Kinas ingripande mot terrorismen?
De nya restriktionerna för resor tillkännagavs i Kommunistpartiets tidning i Yili och i annonser som postades av lokala resebyråer.
Tillkännagivandena sade att människor skulle behöva lämna ett blodprov, fingeravtryck, en röstinspelning och vad polisen kallar en tredimensionell bild.
Politiken trädde i kraft den 1 juni, strax innan Ramadan började. Statstjänstemän och barn är förbjudna från fasta för den muslimska heliga månaden.
Varför finns det spänningar mellan Kina och uigurerna?
Polisen i Kinas nordvästra region Xinjiang ber vissa invånare att lämna DNA-prover och andra biologiska data när de ansöker om resehandlingar.