This study aimed to investigate preferences for, perceived feasibility of and barriers to uptake of hypothetical physical activity promotion strategies among women from socioeconomically disadvantaged neighbourhoods. Semi-structured interviews were conducted with 20 purposively recruited women (18-45 years) living in socioeconomically disadvantaged urban and rural areas of Victoria, Australia. Participants indicated the most and least appealing of nine hypothetical strategies, strategies most likely to use and strategies most likely to increase physical activity. Interviews were digitally recorded and transcribed verbatim. Thematic and interpretive content analyses were used to identify emergent common and contrasting themes. A community centre-based program with free childcare, the provision of a cleaner while physical activity is undertaken and a neighbourhood-based program were the three most popular strategies. Mobile-telephone-delivered text messages, an online interactive diary and subsidized gym memberships were considered least useful. Irrespective of the strategy, components of importance commonly identified were social support; being accountable to someone; having the option of a structured or flexible attendance design; integration of multiple strategies and financial considerations. Issues around trust and privacy and weight loss also emerged as important. The findings provide important insights for the development of physical activity programs targeting socioeconomically disadvantaged women.