A nanocrystalline Ti alloy with a uniform distribution of grains was synthesized using cryogenic mechanical milling. The effects of cryomilling parameters, such as milling time and ball to powder ratio (BPR), on the particle size, grain size, chemistry, and structure of cryomilled Ti powders were investigated using X-ray diffraction (XRD), scanning electron microscopy (SEM), and transmission electron microscopy (TEM). The experimental results show that nanocrystalline Ti powders with a grain size of about 20 nm can be prepared using the cryomilling technique. Compared to SPEX milling at room temperature, cryomilling led to lower contamination levels of oxygen, nitrogen, and iron in the cryomilled Ti powder. The average particle size initially increased from the original 55 μm to a maximum value of 125 μm after 2 h of milling, and then decreased to 44 μm after 8 h of milling. Both the average particle size and the grain size decreased as the BPR increased.