Emerging evidence indicates that long non-coding RNAs (lncRNAs) play important roles in the regulation of many biological processes. Inhibition of plant growth due to deficiency in soil inorganic phosphate (Pi) occurs widely across natural and agricultural ecosystems; however, we know little about the function of plant lncRNAs in response to Pi deficiency. To address this issue, we first identified 10 785 lncRNAs in the legume model species Medicago truncatula by sequencing eight strand-specific libraries. Out of these lncRNAs, 358 and 224 were responsive to Pi deficiency in the leaves and roots, respectively. We further predicted and classified the putative targets of those lncRNAs and the results revealed that they may be involved in the processes of signal transduction, energy synthesis, detoxification, and Pi transport. Finally, we functionally characterized three Phosphate Deficiency-Induced LncRNAs (PDILs) using their corresponding Tnt1 mutants. The results showed that PDIL1suppressed degradation of MtPHO2, which encodes a ubiquitin-conjugating E2 enzyme regulated by miR399, while PDIL2 and PDIL3 directly regulated Pi transport at the transcriptional level. These findings demonstrate that PDILs can regulate Pi-deficiency signaling and Pi transport, highlighting the involvement of lncRNAs in the regulation of responses of plants to Pi deficiency.