In recent years, edible halophytes have received more attention due to their ability to tolerate a wide range of salinities. In Australia, halophytes are used in a broad range of “applications” by Indigenous Communities: in traditional cuisine, as livestock feed and for soil bioremediation. However, very limited scientific information on their nutritional profile and potential bioactivity is available. Therefore, the present study assessed the nutrient and phytochemical composition of Australian grown Seapurslane (SP) (Sesuvium portulacastrum), oldman Saltbush (SB) (Atriplex nummularia) and Seablite (SBL) (Suaeda arbusculoides) to better understand their nutritional ‘value’ and potential bioactivity. SB and SP contained more (p<0.05) fibre than commercial Australian baby spinach (same plant family) which was used as a reference (41.5 vs. 40.4 vs. 33.4 g/100 g dry weight (DW)). Furthermore, these plants can be considered as valuable sources of essential minerals (Ca, Fe, Mg and Na) and trace elements, specifically SBL had the highest contents of Ca and Fe. SB had the highest protein (20.1 g/100 g DW) and fat (2.7 g/100 g DW) content compared to other studied halophytes. The fatty acid profile consisted mainly of palmitic, stearic, oleic, linoleic and α-linolenic acids. A strong antioxidant capacity (total phenolic content and DPPH radical scavenging capacity) indicated that (poly) phenolic compounds are most likely the predominant phytochemicals in this species. These initial results are promising and suggest that Australian indigenous edible halophytes may have the potential to be utilized as functional food ingredients.