National dietary guidelines (DGs) consistently recommend consuming seafood for health benefits, however, the sustainability of increasing seafood consumption is often challenged. Seafood products vary in environmental performance as well as health benefits, yet there is no information integrating the health and ecological impacts of different seafood choices. The first step in optimising improved health and environmental outcomes is to examine more closely the types of seafood being consumed at population and individual levels, to develop the means to increase the intake of seafood that is optimal for human health and the environment. The purpose of this analysis was to better understand the specific types and amounts of seafood consumed by the Australian population, and by socioeconomic subgroups within the population, to determine the relative nutritional content and sustainability of seafood consumed by these groups. Secondary analysis of the Australian Health Survey (AHS) (2011–2013), which reached 32,000 people (25,000 households) was undertaken. The majority of respondents (83%) did not consume any seafood on the day of the survey. Results indicated the proportion of seafood consumers was lowest among adults who were unemployed, had the least education and were the most socio-economically disadvantaged. Crustaceans and farmed fish with low omega 3-content, such as basa and tilapia, were identified as the least nutritious and least sustainable seafood categories. These two categories constituted a substantial amount of total seafood intake for the lowest socio-economic consumers, and over 50% for unemployed consumers. In contrast, consumers in the highest socio-demographic group consumed mainly high trophic level fish (moderate nutrition and sustainability) and farmed fish with high omega-3 content (high nutrition, moderate sustainability). Fewer than 1% of adults or children reported eating seafood identified as both more nutritious and less resource intensive, such as small pelagics or molluscs. Opportunities exist to increase seafood intakes to improve health outcomes by varying current seafood consumption patterns to maximise nutritional outcomes and minimise environmental impacts. Initiatives to promote the health and environmental benefits of seafood should be promoted at the population level, with targeted interventions for specific groups, and should encourage consumption of highly nutritious low resource intensive types of seafood.