Good anticoagulation control in patients during the first months after heart valve surgery is important to prevent thrombotic complications. This is difficult to achieve, partly because the sensitivity to warfarin decreases progressively during approximately three months after valve surgery. A recently developed, simple but aggressive algorithm might improve anticoagulation control in this patient group. It was the objective of this study to evaluate the level of anticoagulation control when a specialised anticoagulation clinic changed from empirical dosing to the use of this new algorithm. In a before-and-after design, a cohort of consecutive patients managed with a new, aggressive dosing algorithm (‘Algorithm cohort’) was compared to a ‘Retrospective cohort’ of similar patients dosed empirically. Primary endpoint was individual time in therapeutic range (ITTR) during the first three months of warfarin therapy. Secondary endpoints included proportion of extreme International Normalised Ratio (INR) results, thrombotic and bleeding complications. Ninety-eight patients were included in the Algorithm cohort, 94 of whom were warfarin-naïve. Two hundred patients were included in the Retrospective cohort. Mean ITTR was 60.1% in the Algorithm cohort versus 48.7% in the Retrospective cohort (p <0.001). Patients in the Algorithm cohort spent 0.5% of time at an INR >5, versus 0.2 % in the Retrospective cohort. There was no major bleeding in either cohort; one patient in each cohort had a thrombotic complication. We demonstrate an improvement of the level of anticoagulation control with the use of a condition-specific, aggressive algorithm, as compared to standard dosing, in patients after heart valve surgery.