We present the results of ab initio modeling of structure of dilute Ti-Fe, a typical representative of quenched Ti-based transition-metal alloys. We have demonstrated that beyond the solubility limit this alloy cannot be described in common terms of substitutional and interstitial alloys. Instead, very stable local clusters are formed in both low-temperature hcp and high-temperature bcc phases of alloys, with almost identical local structures. This gives an example of geometrically frustrated state and explains unusual concentration behavior of Mossbauer spectra discovered long ago for this system.