Elevated inflammatory cytokines (EMCs) at mucosal surfaces have been associated with HIV susceptibility, but the underlying mechanisms remain unclear. We characterized the soluble mucosal proteome associated with elevated cytokine expression in the female reproductive tract. A scoring system was devised based on the elevation (upper quartile) of at least three of seven inflammatory cytokines in cervicovaginal lavage. Using this score, HIV-uninfected Kenyan women were classified as either having EMC (n=28) or not (n=68). Of 455 proteins quantified in proteomic analyses, 53 were associated with EMC (5% false discovery rate threshold). EMCs were associated with proteases, cell motility, and actin cytoskeletal pathways, whereas protease inhibitor, epidermal cell differentiation, and cornified envelope pathways were decreased. Multivariate analysis identified an optimal signature of 16 proteins that distinguished the EMC group with 88% accuracy. Three proteins in this signature were neutrophil-associated proteases that correlated with many cytokines, especially GM-CSF (granulocyte-macrophage colony-stimulating factor), IL-1β (interleukin-1β), MIP-3α (macrophage inflammatory protein-3α), IL-17, and IL-8. Gene set enrichment analyses implicated activated immune cells; we verified experimentally that EMC women had an increased frequency of endocervical CD4(+) T cells. These data reveal strong linkages between mucosal cytokines, barrier function, proteases, and immune cell movement, and propose these as potential mechanisms that increase risk of HIV acquisition.