Distal leg epidermal nerve fiber density (ENFD) is a validated predictor of HIV sensory neuropathy (SN) risk. We assessed how ENFD is impacted by initiation of first-time antiretroviral therapy (ART) in subjects free of neuropathy and how it is altered when mitochondrial toxic nucleoside medications are used as part of ART. Serial changes in proximal thigh and distal leg ENFD were examined over 72 weeks in 150 Thai subjects randomized to a regimen of stavudine (d4T) switching to zidovudine (ZDV) at 24 weeks vs ZDV vs tenofovir (TDF) for the entire duration of study, all given in combination with nevirapine. We found individual variations in ENFD change, with almost equal number of subjects who decreased or increased their distal leg ENFD over 72 weeks and no relationship to nucleoside backbone or to development of neuropathic signs or symptoms. Lower baseline distal leg ENFD and greater increases in mitochondrial oxidative phosphorylation complex I (CI) activity were associated with larger increases in distal leg ENFD over 72 weeks. Distal leg ENFD correlated with body composition parameters (body surface area, body mass index, height) as well as with blood pressure measurements. Assessed together with a companion cross-sectional study, we found that mean distal leg ENFD in all HIV+ subjects was lower than in HIV- subjects but similar among HIV+ groups whether ART-naïve or on d4T with/without neuropathy/neuropathic symptoms. The utility of ENFD as a useful predictor of small unmyelinated nerve fiber damage and neuropathy risk in HIV may be limited in certain populations.