Global expression profiling studies showed that miRNAs are aberrantly expressed in uterine leiomyomas (ULMs) and are involved in ULM pathogenesis. Long noncoding RNAs (lncRNAs) are another group of regulatory RNA whose expression and roles in ULMs have not been explored. In this study, we examined the global expressions of lncRNAs and mRNAs in ULMs using microarray and interrogated their interrelationship through co-expression analysis. We found that lncRNAs and mRNAs were dysregulated in ULMs and the degree of dysregulation was positively correlated with tumor size. Further analysis showed that lncRNAs correlate to their cis mRNAs in expression levels depending on genomic locations and orientations. Moreover, we identified several dysregulated pathways that were correlated to dysregulated lncRNAs. We validated several aberrantly expressed lncRNAs in extended samples and confirmed that AK023096 was down-regulated and chromatin-associated RNA (CAR) Intergenic 10 was up-regulated in the majority of leiomyomas. Knockdown of Intergenic 10 inhibited the proliferation of leiomyoma cells in vitro, indicating its functional importance in ULM pathogenesis. The neighboring protein-coding gene ADAM12 was also downregulated in Intergenic 10 knockdown leiomyoma cells. We showed for the first time that lncRNAs were dysregulated in uterine leiomyomas. Aberrantly expressed lncRNAs may contribute to the pathogenesis of uterine leiomyomas.