Background: Patient medical records are an objective tool for the systematic identification and treatment of tobacco users. The aim of this study was to assess brief intervention tobacco cessation activities documented by physicians in some select tertiary hospitals in Nigeria. Methods: We conducted a cross-sectional descriptive study using information obtained from 1588 randomly selected patient records in six teaching hospitals participating in a study to capacitate physicians to deliver brief advice. Trained data collectors collected data using a uniform checklist prior to the training of the physicians in these hospitals. Results: Of the audited health records, 33.1% of patients had documentation of physicians' inquiry of their tobacco use mostly during out-patient clinics (37%) and by a resident doctor/medical officer (42.9%). Among identified tobacco users, it was documented that 12.9% were offered some form of tobacco cessation advice; readiness to quit was recorded in 2.6%; assistance with quitting was documented for 1.5% of tobacco users, while only 0.8% showed documentation of patient follow-up. Males and patients admitted to the hospital were 1.86 times and 2.14 times respectively more likely to have records of physicians' inquiry of their tobacco use. Patients who had tobacco-related morbidities and the unemployed were also more likely to have records of inquiry of their tobacco use. Conclusions: There was poor documentation of tobacco use by physicians in these hospitals and many opportunities for brief intervention activities were missed. Efforts to educate the physicians on the importance of documenting tobacco use in clinical notes are recommended. Implications: This study provides empirical evidence showing that there is poor documentation of tobacco use inquiry and brief intervention among physicians in tertiary hospitals in Nigeria. Records showing implementation of the 5A's were abysmally low and opportunities for brief intervention may have been missed. In line with the World Health Organization recommendations of Article 14 of the Framework Convention on Tobacco Control, efforts to promote brief intervention among physicians in tertiary hospitals in Nigeria should include an emphasis on appropriate documentation of tobacco control interventions in patient clinical notes.