Background: MicroRNA expression is severely disrupted in carcinogenesis, however limited evidence is available validating results from cell-line models in human clinical cancer specimens. MicroRNA-21 (mir-21) and microRNA-143 (mir-143) have previously been identified as significantly deregulated in a range of cancers including cervical cancer. Our goal was to investigate the expression patterns of several well-studied microRNA species in cervical samples and compare the results to cell line samples. Methodology/Principal Findings: We measured the expression of mir-21 and mir-143 in 142 formalin-fixed, paraffin embedded (FFPE) cervical biopsy tissue blocks, collected from Dantec Oncology Clinic, Dakar, Senegal. MicroRNA expression analysis was performed using Taqman-based real-time PCR assays. Protein immunohistochemical staining was also performed to investigate target protein expression on 72 samples. We found that mir-21 expression increased with worsening clinical diagnosis but that mir-143 was not correlated with histology. These observations were in stark contrast to previous reports involving cervical cancer cell lines in which mir-143 was consistently down-regulated but mir-21 largely unaffected. We also identified, for the first time, that cytoplasmic expression of Programmed Cell Death Protein 4 PDCD4; a known target of mir-21) was significantly lower in women with invasive cervical carcinoma (ICC) in comparison to those with cervical intraepithelial neoplasia (2–3) or carcinoma in situ (CIN2-3/CIS), although there was no significant correlation between mir-21 and PDCD4 expression, despite previous studies identifying PDCD4 transcript as a known mir-21 target. Conclusions: Whilst microRNA biomarkers have a number of promising features, more studies on expression levels in histologically defined clinical specimens are required to investigate clinical relevance of discovery-based studies. Mir-21 may be of some utility in predictive screening, given that we observed a significant correlation between mir-21 expression level and worsening histological diagnosis of cervical cancer.