Discrepancies between clinical guidelines and clinical practice call for practical implementation strategies. This study evaluates the implementation of clinical guidelines for hypertension in general practice with a specific computer-based clinical decision support system (CDSS) as part of the intervention. We carried out a randomized study of general practice health centres in Sør- and Nord-Trøndelag counties in Norway (population 380000). A total of 17 health centres were included, with 24 doctors and 984 patients in the intervention group. Data from 887 patients was used in the analyses. There were 12 health centres with 29 doctors and 1255 patients in the control group. Data from 1127 control patients was used in the analyses. The main outcome measures were doctor's behaviour, measured by adherence to registration of recommended variables in the Norwegian clinical guidelines for hypertension. The aim of the intervention was to lower the fractions of patients without registrations. However, there were no clinically significant differences between the intervention group and the control group for fractions of patients without registration of blood pressure (intervention group 14.3%, control group 14.2%) or serum cholesterol (62.3% vs. 56.8%) during 12 months, nor, during 18 months, for fractions of patients without a registration of cigarette smoking (82.9% vs. 87.1%), cardiovascular inheritance (79.5% vs. 73.4%) and body mass index (81.5% vs. 89.2%). One or several variables necessary for calculation of risk score for myocardial infarction were missing in 91.7% of patients in the intervention group and 91.9% of patients in the control group. Large centre variations were shown for all variables. Implementation of clinical guidelines in the treatment of hypertensive patients in general practice, by means of a CDSS and several procedures for implementation did not result in clinically significant changes in the doctors' behaviour. Of importance are both the lack of user-friendliness of the specific CDSS and problems in performing time-consuming multidimensional procedures.