Background: HIV-associated dementia (HAD) is the most common dementia type in young adults less than 40 years of age. Although the neurotoxins, oxidative/metabolic stress and impaired activity of neurotrophic factors are believed to be underlying reasons for the development of HAD, the genomic basis, which ultimately defines the virus-host interaction and leads to neurologic manifestation of HIV disease is lacking. Therefore, identifying HIV fingerprints on the host gene machinery and its regulation by microRNA holds a great promise and potential for improving our understanding of HAD pathogenesis, its diagnosis and therapy.Results: A parallel profiling of mRNA and miRNA of the frontal cortex autopsies from HIV positive patients with and without dementia was performed using Illumina Human-6 BeadChip and Affymetrix version 1.0 miRNA array, respectively. The gene ontology and pathway analysis of the two data sets showed high concordance between miRNA and mRNAs, revealing significant interference with the host axon guidance and its downstream signalling pathways in HAD brains. Moreover, the differentially expressed (DE) miRNAs identified in this study, in particular miR-137, 153 and 218, based on which most correlations were built cumulatively targeted neurodegeneration related pathways, implying their future potential in diagnosis, prognosis and possible therapies for HIV-mediated and possibly other neurodegenerative diseases. Furthermore, this relationship between DE miRNAs and DE mRNAs was also reflected in correlation analysis using Bayesian networks by splitting-averaging strategy (SA-BNs), which revealed 195 statistically significant correlated miRNA-mRNA pairs according to Pearson's correlation test (P<0.05).Conclusions: Our study provides the first evidence on unambiguous support for intrinsic functional relationship between mRNA and miRNA in the context of HIV-mediated neurodegeneration, which shows that neurologic manifestation in HIV patients possibly occurs through the interference with the host axon guidance and its downstream signalling pathways. These data provide an excellent avenue for the development of new generation of diagnostic/prognostic biomarkers and therapeutic intervention strategies for HIV-associated neurodegeneration.