Background: HIV infection is an emerging problem in Laos. We conducted the first prospective study on intestinal parasites, including opportunistic protozoa, in newly diagnosed HIV infected patients, with or without diarrhea. The aims were to describe the spectrum of infections, to determine their prevalence and to assess their associations with diarrhea, CD4 cell count, place of residence and living conditions. Methodology: One to three stool samples over consecutive days were obtained from 137 patients. The Kato thick smear method, formalin-ethyl concentration and specific stains for coccidia and microsporidia diagnosis were performed on 260 stool samples. Baseline characteristics regarding relevant demographics, place of residence and living conditions, clinical features including diarrhea, were collected using a standardized questionnaire. Principal Findings: The 137 patients were young (median age: 36 years) and severely immunocompromised (83.9% at WHO stage 3 or 4, median CD4 cell count: 41/mm(3)). Diarrhea was present in 43.0% of patients. Parasite infection was found in 78.8% of patients, infection with at least two species in 49.6%. Prevalence rates of protozoan and helminth infections were similar (54.7% and 58.4% respectively). Blastocystis sp. was the most frequent protozoa (26.3%). Cryptosporidium sp., Cytoisospora belli and microsporidia, found at low prevalence rates (6.6%, 4.4%, 2.9%, respectively), were described for the first time in Laos. Cryptosporidium sp. was associated with persistent diarrhea. Strongyloides stercoralis was the most prevalent helminth following Opisthorchis viverrini (20.4% and 47.5% respectively). The most immunocompromised patients, as assessed by a CD4 count <= 50 cells/mm(3), were more likely to be infected with intestinal parasites. Conclusions/Significance: HIV infection was mainly diagnosed at an advanced stage of immunosuppression in Lao patients. Intestinal parasite infections were highly prevalent regardless of their diarrheal status. Opportunistic infections were reported. Improving the laboratory diagnosis of intestinal parasite infections and the knowledge on their local risk factors is warranted.