Tooth brushing is the most common mechanical measure amongst the recommended contemporary oral hygiene procedures engaged in preventive dental therapy. This is to determine the prevalence of toothbrushing habits and their efficacy in the removal of tooth deposits and resultant clinical periodontal health of the participants. This study, involved 250 first-time patients the Family Medicine Department at the Lagos State University Teaching Hospital (LASUTH), Ikeja, Lagos. Data collection was conducted using a self-administered questionnaire to obtain the sociodemographic data and the participants' toothbrushing habits. The efficacy of toothbrushing was assessed by evaluating the Oral hygiene index (OHI) and the periodontal status of the participants. Appropriate descriptive statistics were carried out. Pearson’s chi-square analysis was done to determine the bivariate relationship of the covariates and their efficacy, while regression analysis was done to assess the multivariate relationship. Statistical significance was determined at p≤ 0.05. The mean age of the participants was 40.1 ± 18.4 years; the 20-29-year-olds had the highest percentage with good oral hygiene, 20(30.3%). Those who brush their teeth more than twice daily had the highest percentage with good oral hygiene,4(66.7%) (p=0.002) and healthy periodontium, 4(66.7%) (p=0.03). Toothbrushing duration was significantly associated with the oral hygiene status (p=0.001). Those who brush their teeth >120 seconds had the highest percentage with good oral hygiene, 44(65.7%), and healthy periodontium, 39(58.2%) (p=0.001). Toothbrushing duration was the only habit that was independently associated with the oral hygiene status (p=0.001). Toothbrushing duration, age groups and male sex were independently associated with the periodontal status (p<0.05). Oral health education and counselling have to be holistic, as many of the factors and habits operate jointly in the provision of healthy oral hygiene and periodontal health. Brushing for up to 3 minutes will be more beneficial for the overall health of individuals.