Cervicovaginal microbiome dysbiosis is associated with increased prevalence and incidence of sexually transmitted infections including HIV. We compared the cervicovaginal proteome as characterised by mass-spectrometry of four groups of African female sex workers (total N=50) grouped by microbiome composition as characterised by 16S rDNA microarray. Group 1 had a Lactobacillus crispatus-dominated microbiome, group 2 a L. iners-dominated microbiome, and groups 3 and 4 had a microbiome containing multiple genera of anaerobic bacteria, with group 3 representing transition to or from dysbiosis and group 4 full dysbiosis. 82 human proteins were differentially abundant among the groups, either showing an increasing or decreasing trend from microbiome groups 1 to 4. Proteins that increased included proteasome subunits and other proteins involved in catabolic metabolism, actin organising proteins and proteins involved in the immune response. Proteins that decreased included antiproteases, keratins, and cornified envelope proteins. We also compared the abundance of pre-defined proteins of interest among microbiome groups: markers of cell type, inflammation, and cell death, and mucins. The dysbiotic groups had increased abundance of proteins unique to lymphocytes and macrophages, pro-inflammatory cytokines, cell death markers, and MUC5B. We conclude that the cervicovaginal human proteome is associated with the cervicovaginal microbiome in a dose-response manner. The changes are likely caused by a pro-inflammatory influx of immune cells and an increase of cell death in dysbiosis. Dysbiosis-associated immune activation, breaches in epithelial integrity, altered mucin balance, and altered protease-antiprotease balance may all contribute to the increased risk of HIV transmission when cervicovaginal dysbiosis is present.