Reducing dietary phosphorus (P) is a common approach to reduce effluent P outputs. The potential resulting P-deficiency is known to negatively impact fish bone condition and might result in vertebral deformities. To date, no large-scale study involving deep sequencing of the bone transcriptome has been conducted in salmonids and vertebral molecular changes remain poorly described. This study aims to provide the first comprehensive vertebral transcriptome for rainbow trout (Oncorhynchus mykiss) to allow functional and quantitative expression studies. Fish weighing 60.8 ± 1.6 g, were fed for 27 weeks using two practical diets having 0.29% (deficient) and 0.45% (sufficient) available phosphorus (P), respectively. Deep sequencing was conducted using HiSeq2000 Illumina 100 paired-end technology from pooled P-deficient and P-sufficient fish and individuals displaying vertebral deformities. Over 140 million trimmed paired-end reads were assembled de novo with Trinity and resulted in 679,869 transcripts with a mean length of 542.5 bp. From these sequences, 340,747 matched with referenced ESTs from rainbow trout. Furthermore, 141,909 and 117,564 sequences were functionally annotated against Nr and Uniprot databases, respectively. Interestingly, we observed putative homologue sequences for most of the key components involved in bone formation and turnover in mammals.