Seaweeds have a long history as a resource for polysaccharides/hydrocolloids extraction for use in the food industry due to their functionality as stabilizing agents. In addition to the carbohydrate content, seaweeds also contains a significant amount of protein, which may find application in food and feed. Here, we present a novel combination of transcriptomics, proteomics, and bioinformatics to determine the protein composition in two pilot-scale extracts from Eucheuma denticilatum (Spinosum) obtained via hot-water extraction. The extracts were characterized by qualitative and quantitative proteomics using LC-MS/MS and a de-novo transcriptome assembly for construction of a novel proteome. Using label-free, relative quantification, we were able to identify the most abundant proteins in the extracts and determined that the majority of quantified protein in the extracts (>75%) is constituted by merely three previously uncharacterized proteins. Putative subcellular localization for the quantified proteins was determined by bioinformatic prediction, and by correlating with the expected copy number from the transcriptome analysis, we determined that the extracts were highly enriched in extracellular proteins. This implies that the method predominantly extracts extracellular proteins, and thus appear ineffective for cellular disruption and subsequent release of intracellular proteins. Ultimately, this study highlight the power of quantitative proteomics as a novel tool for characterization of alternative protein sources intended for use in foods. Additionally, the study showcases the potential of proteomics for evaluation of protein extraction methods and as powerful tool in the development of an efficient extraction process.