Studies of the transcriptional output of the human and mouse genomes have revealed that there are many more transcripts produced than can be accounted for by predicted protein-coding genes. Using a custom microarray, we have identified 184 non-coding RNAs that exhibit more than twofold up- or down-regulation upon differentiation of C2C12 myoblasts into myotubes. Here, we focus on the Men epsilon/beta locus, which is up-regulated 3.3-fold during differentiation. Two non-coding RNA isoforms are produced from a single RNA polymerase II promoter, differing in the location of their 3' ends. Men epsilon is a 3.2-kb polyadenylated RNA, whereas Men beta is an approximately 20-kb transcript containing a genomically encoded poly(A)-rich tract at its 3'-end. The 3'-end of Men beta is generated by RNase P cleavage. The Men epsilon/beta transcripts are localized to nuclear paraspeckles and directly interact with NONO. Knockdown of MEN epsilon/beta expression results in the disruption of nuclear paraspeckles. Furthermore, the formation of paraspeckles, after release from transcriptional inhibition by DRB treatment, was suppressed in MEN epsilon/beta-depleted cells. Our findings indicate that the MEN epsilon/beta non-coding RNAs are essential structural/organizational components of paraspeckles.