Perioperative stroke can occur following 0.2-0.3% of general surgical and orthopedic procedures. We are reporting a patient who developed multiple strokes in the immediate postoperative period following total knee replacement, where etiological workup revealed multiple pulmonary arteriovenous fistulae (PAVF). The significance of PAVF with paradoxical embolism in perioperative settings has rarely been reported in the literature.