We have predicted miRNAs, their targets and lncRNAs from the genome of Brassica oleracea along with their functional annotation. Selected miRNAs and their targets are experimentally validated. Roles of these non-coding RNAs in post-transcriptional gene regulation are also deciphered. Cauliflower (Brassica oleracea var. Botrytis) is an important vegetable crop for its dietary and medicinal values with rich source of vitamins, dietary fibers, flavonoids and antioxidants. MicroRNAs (miRNAs) are small non-coding RNAs (ncRNAs), which regulate gene expression by inhibiting translation or by degrading messenger RNAs (mRNAs). On the other hand, long non-coding RNAs (lncRNAs) are responsible for the up regulation and the down regulation of transcription. Although the genome of cauliflower is reported, yet the roles of these ncRNAs in post-transcriptional gene regulation (PTGR) remain elusive. In this study, we have computationally predicted 355 miRNAs, of which 280 miRNAs are novel compared to miRBase 22.1. All the predicted miRNAs belong to 121 different families. We have also identified 934 targets of 125 miRNAs along with their functional annotation. These targets are further classified into biological processes, molecular functions and cellular components. Moreover, we have predicted 634 lncRNAs, of which 61 are targeted by 30 novel miRNAs. Randomly chosen 10 miRNAs and 10 lncRNAs are experimentally validated. Five miRNA targets including squamosa promoter-binding-like protein 9, homeobox-leucine zipper protein HDG12-like, NAC domain-containing protein 100, CUP-SHAPED COTYLEDON 1 and kinesin-like protein NACK2 of four miRNAs including bol-miR156a, bol-miR162a, bol-miR164d and bol-miR2673 are also experimentally validated. We have built network models of interactions between miRNAs and their target mRNAs, as well as between miRNAs and lncRNAs. Our findings enhance the knowledge of non-coding genome of cauliflower and their roles in PTGR, and might play important roles in improving agronomic traits of this economically important crop.