Many patients using warfarin are being managed in primary care and typically achieve a lower time in therapeutic range (TTR) for the international normalized ratio (INR) than patients in specialized care. A simple warfarin maintenance dosing tool could assist primary care physicians with improving TTR. We tested whether a simple warfarin maintenance dosing algorithm can improve TTR compared with usual care among Canadian primary care physicians. Primary care practices managing warfarin therapy without an anticoagulation clinic, computer decision support system or patient self-management tools enrolled 10-30 patients with target INR range 2-3. Practices were randomized to manage warfarin maintenance with the algorithm, or as usual in 2009-2010. Primary outcome was the mean individual patient TTR, and was compared between groups with adjustment for clustering within practices. There were 13 practices randomized to the Algorithm and 15 practices to Control, enrolling 240 and 297 patients respectively, with a mean follow-up of 280 days. Mean (standard deviation; SD) TTR before the study was comparable between groups [68 % (SD 26) for usual care vs. 70 % (SD 27) for the algorithm; p = 0.49]. Dosing decisions during the study in the algorithm group were more often in agreement with the algorithm's recommendations than with usual care (81 vs. 91 %; p < 0.0001). Mean study TTR of the algorithm group was not superior to usual care: [72.1 (SE 1.7) vs. 71.4 % (SE 1.5) respectively; p = 0.73]. The simple warfarin maintenance dosing algorithm did not improve TTR compared with usual care among Canadian primary care practices.