MicroRNAs regulate several aspects of tumorigenesis and cancer progression. Most cancer tissues are archived formalin-fixed and paraffin-embedded (FFPE). While microRNAs are a more stable form of RNA thought to withstand FFPE-processing and degradation there is only limited evidence for the latter assumption. We examined whether microRNA profiling can be successfully conducted on FFPE cancer tissues using SOLiD ligation based sequencing. Tissue storage times (2-9 years) appeared to not affect the number of detected microRNAs in FFPE samples compared to matched frozen samples (paired t-test p>0.7). Correlations of microRNA expression values were very high across microRNAs in a given sample (Pearson's r = 0.71-0.95). Higher variance of expression values among samples was associated with higher correlation coefficients between FFPE and frozen tissues. One of the FFPE samples in this study was degraded for unknown reasons with a peak read length of 17 nucleotides compared to 21 in all other samples. The number of detected microRNAs in this sample was within the range of microRNAs detected in all other samples. Ligation-based microRNA deep sequencing on FFPE cancer tissues is feasible and RNA degradation to the degree observed in our study appears to not affect the number of microRNAs that can be quantified.