Background: Continued low adherence to physical activity recommendations illustrates the need to refine intervention strategies and increase their effectiveness. The purpose of this study was to conduct formative research related to the development of a next generation of computer-tailored interventions that use online tailored video-messages to increase physical activity. Methods: Five focus groups (n = 30), aimed at males and females, aged between 35 and 60 years, that do not meet the physical activity recommendation, were conducted to allow in-depth discussion of various elements related to the development of an online video-tailored intervention. In addition, a series of questions were delivered to a random sample (n = 1261) of Australians, using CATI survey technology, to gain more information and add a quantitative assessment of feasibility related to the development of the intervention. Focus group data was transcribed, and summarised using Nvivo software. Descriptive and frequency data of the survey was obtained using SPSS 18.0. Results: Nearly all of the focus group participants supported the concept of a video-tailored intervention and 35.8% of survey participants indicated that they would prefer a video-based over a text-based intervention. Participants with a slow internet-connection displayed a lower preference for video-based advice (31.9%); however less than 20% of the survey sample indicated that downloading videos would be slow. The majority of focus group and survey participants did not support the idea of using mobile phones to receive this kind of intervention and indicated that video-tailored messages should be shorter than 5 minutes. Video-delivery of content is very rich in information, which increases the challenge to appropriately tailor content to participant characteristics; focus group outcomes indicated a large diversity in participant preferences. 52.4% of survey participants indicated that the videos should be convincing and motivating. Conclusions: These results provide valuable information to develop an innovative video-tailored physical activity intervention. The results support the feasibility of such intervention, both in terms of users being ready to participate in it, as well as from a point of view whereby current internet infrastructure is able to cope with thedemands of downloading videos. Though promising, a number of specific challenges in the development of these interventions were identified (e.g. the videos need to be short, made professionally, and tailor to a larger number of variables) and will need to be overcome in the development and evaluation of this new type of physical activity intervention.