Increasing evidence shows that long non-coding RNAs (lncRNAs) function as important regulatory factors during plant development, but few reports have examined lncRNAs in trees. Here, we report our genome-scale identification and characterization of lncRNAs differentially expressed in the xylem of tension wood, opposite wood and normal wood in Populus tomentosa, by high-throughput RNA sequencing. We identified 1,377 putative lncRNAs by computational analysis, and expression and structure analyses showed that the lncRNAs had lower expression levels and shorter lengths than protein-coding transcripts in Populus. Of the 776 differently expressed (log2FC ≥1 or ≤-1, FDR ≤0.01) lncRNAs, 389 could potentially target 1,151 genes via trans-regulatory effects. Functional annotation of these target genes demonstrated that they are involved in fundamental processes, and in specific mechanisms such as response to stimuli. We also identified 16 target genes involved in wood formation, including cellulose and lignin biosynthesis, suggesting a potential role for lncRNAs in wood formation. In addition, three lncRNAs harbor precursors of four miRNAs, and 25 were potentially targeted by 44 miRNAs where a negative expression relationship between them was detected by qRT-PCR. Thus, a network of interactions among the lncRNAs, miRNAs and mRNAs was constructed, indicating widespread regulatory interactions between non-coding RNAs and mRNAs. Lastly, qRT-PCR validation confirmed the differential expression of these lncRNAs, and revealed that they have tissue-specific expression in P. tomentosa. This study presents the first global identification of lncRNAs and their potential functions in wood formation, providing a starting point for detailed dissection of the functions of lncRNAs in Populus.