LncRNAs, which represent one of the most highly expressed classes of ncRNAs in the brain, are becoming increasingly interesting with regard to brain functions and disorders. However, changes in the expression of regulatory lncRNAs in Major Depressive Disorder (MDD) have not yet been reported. Using microarrays, we profiled the expression of 34834 lncRNAs and 39224 mRNAs in peripheral blood sampled from MDD patients as well as demographically-matched controls. Among these, we found that 2007 lncRNAs and 1667 mRNAs were differentially expressed, 17 of which were documented as depression-related gene in previous studies. Gene Ontology (GO) and pathway analyses indicated that the biological functions of differentially expressed mRNAs were related to fundamental metabolic processes and neurodevelopment diseases. To investigate the potential regulatory roles of the differentially expressed lncRNAs on the mRNAs, we also constructed co-expression networks composed of the lncRNAs and mRNAs, which shows significant correlated patterns of expression. In the MDD-derived network, there were a greater number of nodes and connections than that in the control-derived network. The lncRNAs located at chr10:874695-874794, chr10:75873456-75873642, and chr3:47048304-47048512 may be important factors regulating the expression of mRNAs as they have previously been reported associations with MDD. This study is the first to explore genome-wide lncRNA expression and co-expression with mRNA patterns in MDD using microarray technology. We identified circulating lncRNAs that are aberrantly expressed in MDD and the results suggest that lncRNAs may contribute to the molecular pathogenesis of MDD.