Background: Despite many associated health benefits of regular participation in physical activity during pregnancy, few Australian pregnant women are sufficiently active. As such, efforts to promote physical activity during pregnancy are required to improve public health. Web-based interventions, and particularly those utilising computer-tailoring, offer a promising approach due to their potential for wide-reach and the delivery of interactive and on-going support in a sustainable way. While such interventions have been shown to be effective for promoting physical activity in a number of populations, no such intervention has been conducted among pregnant women. Thus, the aim of this study was to assess the feasibility and preliminary efficacy of a computer-tailored web-based intervention (Fit4Two) designed to promote moderate-vigorous physical activity (MVPA) among pregnant women. Methods: 57 pregnant women were randomised into either (1) a tailored intervention group (TIG) that received tailored MVPA advice based on Social Cognitive Theory, and access to a resource library consisting of articles relating to MVPA during pregnancy or (2) a standard information group (SIG) that only received access to the resources library. Participants were assessed at baseline and two months post-baseline. Outcome measures included MVPA (min), website usage (page views, number of visits, minutes spent per visit), website usability (SUS Scale), and process evaluation data. Standard errors for means were calculated using non-parametric bootstrapping. Treatment effects (group and time) were assessed using the Wilcox rank-sum test. Results: Retention was 75%, with no between-group difference (p = 0.067). Both groups significantly increased MVPA. The mean increase in MVPA was higher in the TIG (115 min/week, 95%CI:65.70;186.66) than the SIG (85 min/week, 95%CI:50.58;136.62), however this difference was not significant (p = 0.74). The TIG viewed significantly more web-pages than the SIG (Mdiff = 45.97, 95%CI:19.64;72.31, p < 0.001). Average number of sessions (Mdiff = 1.36, 95%CI:0.88;3.6) and time on site (Mdiff = 1.34, 95%CI:−2.07;4.74) were also higher among TIG participants, however these differences were not significant. Overall, usability of the website was ranked as good-excellent (75/100) and participants’ perceptions of the website were positive. Discussion: The positive findings associated with both study arms suggest that the delivery of physical activity advice online to pregnant women is feasible, well accepted and associated with increases in physical activity, at least in the short term. Preliminary findings suggest the tailored intervention may lead to greater physical activity changes, however a fully powered trial is needed to explore this further and evaluate longer-term intervention effects.