(1) Background: Cold stress affects growth and development in plants and is a major environmental factor that decreases productivity. Over the past two decades, the advent of next generation sequencing (NGS) technologies has opened new opportunities to understand the molecular bases of stress resistance by enabling the detection of weakly expressed transcripts and the identification of regulatory RNAs of gene expression, including microRNAs (miRNAs). (2) Methods: In this study, we performed time series sRNA and mRNA sequencing experiments on two pea (Pisum sativum L., Ps) lines, Champagne frost-tolerant and Térèse frost-sensitive, during a low temperature treatment versus a control condition. (3) Results: An integrative analysis led to the identification of 136 miRNAs and a regulation network composed of 39 miRNA/mRNA target pairs with discordant expression patterns. (4) Conclusions: Our findings indicate that the cold response in pea involves 11 miRNA families as well as their target genes related to antioxidative and multi-stress defense mechanisms and cell wall biosynthesis.