Different types of marriage patterns such as polygyny and levirate marriages are expected to be risks for HIV infection in communities where such practices are common. Previous to this study a 6.5% HIV prevalence was reported in Gambella, a region where polygyny and levirate marriages are common. We conducted a cross sectional study to assess the sero-prevalence of HIV infection across different marriage patterns using 424 individuals attending Gambella Hospital. The overall HIV prevalence in the current study was 8.5%, with a prevalence of 3.5%, 4.0%, and 1.0% among monogamy, polygyny and unmarried individuals, respectively. Polygyny, illiteracy, levirate and gift marriage, rural residency, being house wife, lack of knowledge about HIV/AIDS, absence of discussion about HIV with partner, lack of knowledge about VCT and not being tested before were factors that showed statistically significant association with HIV infection at least in a bivariate analysis. The findings of this study indicated the need for fighting harmful traditional practices such as polygyny and levirate marriage through community dialogue and implementation of preventive measures to tackle HIV infection in Gambella administrative region in particular which may also hold true in some other parts of the country in general.