Administration of preoperative antimicrobial prophylaxis, often with a cephalosporin, is the mainstay of surgical site infection prevention guidelines. Unfortunately, due to prevalent misconceptions, patients labeled as having a penicillin allergy often receive alternate and less-effective antibiotics, placing them at risk of a variety of adverse effects including increased morbidity and higher risk of surgical site infection. The perioperative physician should ascertain the nature of previous reactions to aid in determining the probability of the prevalence of a true allergy. Penicillin allergy testing may be performed but may not be feasible in the perioperative setting. Current evidence on the structural determinants of penicillin and cephalosporin allergies refutes the misconception of cross-reactivity between penicillins and cefazolin, and there is no clear evidence of an increased risk of anaphylaxis in cefazolin-naive, penicillin-allergic patients. A clinical practice algorithm for the perioperative evaluation and management of patients reporting a history of penicillin allergy is presented, concluding that cephalosporins can be safely administered to a majority of such patients.