The availability of the first complete genome sequence of the marine flowering plant Zostera marina (commonly known as seagrass) in early 2016, is expected to significantly raise the impact of seagrass proteomics. Seagrasses are marine ecosystem engineers that are currently declining worldwide at an alarming rate due to both natural and anthropogenic disturbances. Seagrasses (especially species of the genus Zostera) are compromised for proteomic studies primarily due to the lack of efficient protein extraction methods because of their recalcitrant cell wall which is rich in complex polysaccharides and a high abundance of secondary metabolites in their cells. In the present study, three protein extraction methods that are commonly used in plant proteomics i.e., phenol (P); trichloroacetic acid/acetone/SDS/phenol (TASP); and borax/polyvinyl-polypyrrolidone/phenol (BPP) extraction, were evaluated quantitatively and qualitatively based on two dimensional isoelectric focusing (2D-IEF) maps and LC-MS/MS analysis using the two most abundant Australian seagrass species, namely Zostera muelleri and Posidonia australis. All three tested methods produced high quality protein extracts with excellent 2D-IEF maps in P. australis. However, the BPP method produces better results in Z. muelleri compared to TASP and P. Therefore, we further modified the BPP method (M-BPP) by homogenizing the tissue in a modified protein extraction buffer containing both ionic and non-ionic detergents (0.5% SDS; 1.5% Triton X-100), 2% PVPP and protease inhibitors. Further, the extracted proteins were solubilized in 0.5% of zwitterionic detergent (C7BzO) instead of 4% CHAPS. This slight modification to the BPP method resulted in a higher protein yield, and good quality 2-DE maps with a higher number of protein spots in both the tested seagrasses. Further, the M-BPP method was successfully utilized in western-blot analysis of phosphoenolpyruvate carboxylase (PEPC—a key enzyme for carbon metabolism). This optimized protein extraction method will be a significant stride toward seagrass proteome mining and identifying the protein biomarkers to stress response of seagrasses under the scenario of global climate change and anthropogenic perturbations.