We propose a new approach to developing of graded-index chalcogenide fibers. Since chalcogenide glasses are incompatible with current vapor deposition techniques, the arbitrary refractive index gradient is obtained by means of core nanostructurization by the effective medium approach. We study the influence of graded-index core profile and the core diameter on the fiber dispersion characteristics. Flat, normal dispersion profiles across the mid-infrared transmission window of the assumed glasses are easily obtained for the investigated core nanostructure layouts. Nonlinear propagation simulations enable to expect 3.5-8.5 µm spectrum of coherent, pulse preserving supercontinuum. Fabrication feasibility of the proposed fiber is also discussed.