Although severe vitamin B12 deficiency is rare in the United States, recent increases in the adoption of vegan lifestyles have led to a significant rise in the rates of B12 deficiency, along with its hematologic and neurologic sequelae, the latter of which is often irreversible. We describe a case of a 39-year-old male who presented with a several-month history of progressively worsening word-finding difficulties, shortness of breath, and a four-day history of bilateral hand numbness and tingling. Laboratory data revealed pancytopenia with profound anemia. Markers of hemolysis were positive, including elevated indirect bilirubin, disproportionately elevated lactate dehydrogenase (LDH), low haptoglobin, negative direct anticoagulant test, and hypoproliferative reticulocyte index. Blood smear revealed hypersegmented neutrophils and macrocytosis. Vitamin B12 levels were undetectable, and anti-intrinsic factor and parietal cell antibodies were negative. A thorough history revealed a 20-year history of strict veganism without B12 supplementation. He was transfused with packed red blood cells and started on subcutaneous B12 injections with rapid improvement of his symptoms. Early recognition of B12 deficiency causing the constellation of pancytopenia, hemolytic anemia, and neurologic symptoms is vital in preventing irreversible neurologic sequelae. This case also highlights the importance of accurate history taking to aid in early diagnosis of B12 deficiency, especially in the context of rising rates of veganism in the United States.