Small-scale coastal fisheries contribute directly and indirectly to the food and nutrition security of marine-dependent households. Fishers can apportion part of their catch for household consumption or use the income earned to purchase staples and other desired foods. Fish are an important animal-source food rich in micronutrients essential for cognitive development of children and for adult health, and a valuable addition to rice-based diets. Furthermore, the engagement of women in fisheries value chains and increased control over income may facilitate decision-making which improves nutrition outcomes for women and their children. Despite these contributions, food insecurity remains prevalent in many low and middle income fish-producing countries. This paper reports findings from an exploration of the interplaying factors leading to food and nutrition insecurity in three marine-dependent coastal communities in eastern Indonesia, focusing on the consumption pathway, that is, the contribution of fish to the diets and nutrition of women and children. The research was undertaken as a mixed-methods case study. The study found that over 50% of mother-child pairs failed to meet the minimum recommended dietary diversity, and, while fish was the main animal-source food in diets, the introduction of fish to infant and young child diets was delayed due to fears of allergies and illnesses. Moreover, access to nutrient-dense foods was affected by variable and insufficient income from fisheries-based livelihoods, isolation from markets, and the broader food environment. Given the shift towards ‘nutrition-sensitive interventions’ to improve the livelihoods and well-being of fisher households, these results highlight the need for analysis of the intra-household sharing of fish within fisher households, culturally-appropriate strategies to improve the quality of family and especially complementary foods, and efforts to increase physical access to nutrient-dense foods.