c. 1300, doctour, "Church father," from Old French doctour and directly from Medieval Latin doctor "religious teacher, adviser, scholar," in classical Latin "teacher," agent noun from docere "to show, teach, cause to know," originally "make to appear right," causative of decere "be seemly, fitting," from PIE root *dek- "to take, accept."
Meaning "holder of the highest degree in a university, one who has passed all the degrees of a faculty and is thereby empowered to teach the subjects included in it" is from late 14c. Hence "teacher, instructor, learned man; one skilled in a learned profession" (late 14c.).
The sense of "medical professional, person duly licensed to practice medicine" (replacing native leech (n.2)) grew gradually out of this from c., 1400, though this use of the word was not common until late 16c. The transitional stage is exemplified in Chaucer's Doctor of phesike (Latin physica came to be used extensively in Medieval Latin for medicina).
That no man ... practyse in Fisyk ... but he be Bacheler or Doctour of Fisyk, havynge Lettres testimonyalx sufficeantz of on of those degrees of the Universite. [Rolls of Parliament, 1421]
Similar usage of the equivalent of doctor is colloquial in most European languages: Italian dottore, French docteur, German doktor, Lithuanian daktaras, though these typically are not the main word in those languages for a medical healer. For similar evolution, compare Sanskrit vaidya- "medical doctor," literally "one versed in science." German Arzt, Dutch arts are from Late Latin archiater, from Greek arkhiatros "chief healer," hence "court physician." French médecin is a back-formation from médicine, replacing Old French miege, from Latin medicus.
Phrase what the doctor ordered "just the thing" is attested by 1914.