Cerebral air embolism (CAE) is an infrequently reported complication of routine medical procedures. We present two cases of CAE. The first patient was a 55-year-old male presenting with vomiting and loss of consciousness one day after his hemodialysis session. Physical exam was significant for hypotension and hypoxia with no focal neurologic deficits. Computed tomography (CT) scan of head showed gas in cerebral venous circulation. The patient did not undergo any procedures prior to presentation, and his last hemodialysis session was uneventful. Retrograde rise of venous air to the cerebral circulation was the likely mechanism for venous CAE. The second patient was a 46-year-old female presenting with fever, shortness of breath, and hematemesis. She was febrile, tachypneic, and tachycardic and required intubation and mechanical ventilation. An orogastric tube inserted drained 2500 mL of bright red blood. Flexible laryngoscopy and esophagogastroduodenoscopy were performed. She also underwent central venous catheter placement. CT scan of head performed the next day due to absent brain stem reflexes revealed intravascular air within cerebral arteries. A transthoracic echocardiogram with bubble study ruled out patent foramen ovale. The patient had a paradoxical CAE in the absence of a patent foramen ovale.