The effectiveness and costs of very early rehabilitation after stroke are unknown. This study assessed the cost effectiveness of very early mobilisation in addition to standard care (VEM) compared with standard care alone (SC).Cost-effectiveness analysis alongside a phase II, multi-centre, randomised controlled trial (RCT) with blinded outcome assessments. Less than 24 h after stroke, patients were recruited from two stroke units and randomised to receive VEM or SC. The intervention continued until discharge or 14 days, whichever was sooner. The efficacy measure was a dichotomised modified Rankin Scale (mRS) at 3 months with mRS < or =2 representing good outcome. Costs were determined from medical records and patient interviews at 3, 6 and 12 months. National average (where available) or local costs were applied for the reference year 2004. Differences in mean total costs at 3 and 12 months were tested using t test assuming unequal variances. An incremental cost-effectiveness ratio was calculated and probabilistic uncertainty analysis was undertaken.The sample consisted of 38 VEM and 33 SC patients. A trend for good outcome with VEM compared to SC was found (adjusted OR 4.10, 95% CI 0.99-16.88, p = 0.051). Patients receiving VEM incurred significantly less costs at 3 months (AUD 13,559) compared with SC (AUD 21,860; p = 0.02). This difference in mean per patient total cost persisted at the 12-month assessment (VEM: AUD 17,564; SC: AUD 29,750; p = 0.03). VEM was found to be a 'dominant' (more effective, less cost) intervention when compared to SC at 3 months.These findings provide preliminary evidence that VEM is likely to be cost-effective. A large RCT is currently underway to confirm the cost effectiveness of VEM.