Seaweeds have been incorporated in the daily diet of several human cultures since ancient times, due to their nutritional characteristics and healthy properties. The brown seaweeds Undaria pinnatifida, Saccharina latissima, Sacchoriza polyschides, and Laminaria ochroleuca were collected in the Viana do Castelo (Portugal) bay to assess their proximate composition analysis. As a result, the algal biomass was dried, and its moisture and ash content were determined. The dried biomass was then analyzed for total nitrogen/total protein (using the Kjeldahl method), total fiber content (through fiber analyzer digestion), total lipids (in a Soxhlet apparatus), and fatty acid characterization (by gas chromatography-mass spectrometry). Apart from phosphorus, which was analyzed by spectrophotometry, the ashes were employed for mineral and trace element characterization via dry mineralization and quantified using flame atomic absorption spectrometry. Moreover, the total phenolic content was assessed spectrophotometrically by the Folin-Ciocalteu method in the algal aqueous extracts. Analyses showed that their protein concentrations ranged from 12 to 24% dry weight (DW), while lipid concentrations varied between 0.51% and 1.52% DW. Regarding the carbohydrate concentration in these seaweeds, a concentration between 48% and 60% DW was observed. The S. polyschides had the highest overall total phenolic content (6.19 × 10−3 g GAE/100 g of dried algae), while L. ochroleuca had the lowest amount (3.72 × 10−3 g GAE/100 g of dried algae). U. pinnatifida had the highest total fatty acid content (35.13 mg/g DW), whereas S. latissima presented the lowest value (22.59 mg/g DW). Significant concentrations of highly unsaturated fatty acids (HUFA) were observed in both seaweeds, with U. pinnatifida having the highest value (10.20 mg/g DW) and S. latissima the lowest content (4.81 mg/g DW). It is also highlighted that these seaweeds have a nutritional relevance as a source of essential nutrients, including nitrogen, potassium, sodium, calcium, magnesium, and iron.