Inclusion Criteria:  Diagnosis:  Phase I cohort: Adults >= 18 years with relapsed/refractory FLT3-mutated AML or myelodysplastic syndrome (MDS) that is intermediate-2 or high-risk by the International Prognostic Scoring System  Phase II cohort A: Adults >= 18 years with newly diagnosed FLT3-mutated AML. Patients should meet the following criteria:  Confirmed newly diagnosed AML with FLT3 mutation  Ineligible for induction therapy defined as  Either age >= 75 Or 18-74 with at least one comorbidity (congestive heart failure [CHF] requiring therapy or ejection fraction [EF] =< 50%, diffusion capacity of the lung for carbon monoxide [DLCO] =< 65% or forced expiratory volume in 1 second [FEV1] =< 65%, or Eastern Cooperative Oncology Group [ECOG] 2 or 3, or other significant co-morbidity precluding use of cytotoxic chemotherapy as approved by the principal investigator (PI) Phase II cohort B: Adults >= 18 years with relapsed/refractory FLT3-mutated AML or MDS that is intermediate-2 or high-risk by the International Prognostic Scoring System who have received 1 prior therapy For all cohorts, patients with either FLT3-ITD or FLT3 D835 mutations will be eligible Performance status =< 3 (Eastern Cooperative Oncology Group [ECOG] scale) Total serum bilirubin =< 2.5 x upper limit of normal (ULN), unless due to Gilbert's syndrome, hemolysis or the underlying leukemia approved by the PI Alanine aminotransferase (ALT) or aspartate aminotransferase (AST) =< 3 x ULN, unless due to the underlying leukemia approved by the PI Creatinine clearance >= 30 mL/min Ability to swallow Signed informed consent Hydroxyurea or one dose of cytarabine up to 1000 mg is allowed to reduce the white blood cell (WBC) to less than 25 x 10^9/L prior to initiation of study treatment  Exclusion Criteria:  Prior therapies  Phase I cohort: No restriction based on prior therapies Phase II cohort A: Patients with prior therapy for AML are not eligible. Prior therapy for antecedent hematologic disorder is allowed including prior hypomethylating agent (HMA) therapy for MDS. Prior hydroxyurea or cytarabine given for purposes of cytoreduction is also allowed. Prior all trans-retinoic acid given for presumed acute promyelocytic leukemia is also allowed Phase II cohort B: Patients with >= 3 prior lines of therapy are not eligible. Stem cell transplantation, treatment given only for cytoreductive purposes (e.g. hydroxyurea), and growth factors do not count as lines of therapy for this purpose. Prior therapy with venetoclax is allowed Prior treatment with gilteritinib Patients suitable for and willing to receive intensive induction chemotherapy (for Phase II cohort A only) Congenital long QT syndrome or corrected QT (QTc) > 450 msec. Repeat electrocardiograms (EKGs) after correction of electrolytes or discontinuation of QT prolonging medications are allowed to meet entry criteria Active serious infection not controlled by oral or intravenous antibiotics (e.g. persistent fever or lack of improvement despite antimicrobial treatment) Active grade III-V cardiac failure as defined by the New York Heart Association Criteria Active central nervous system leukemia Known history of human immunodeficiency virus (HIV) seropositive  Known hepatitis B surface antigen seropositive or known or suspected active hepatitis C infection  Note: Patients who have isolated positive hepatitis B core antibody (i.e., in the setting of negative hepatitis B surface antigen and negative hepatitis B surface antibody) must have an undetectable hepatitis B viral load. Patients who have positive hepatitis C antibody may be included if they have an undetectable hepatitis C viral load Patients with a prior or concurrent malignancy whose natural history or treatment is not anticipated to interfere with the safety or efficacy assessment of the investigational regimen may be included only after discussion with the PI Consumed strong inducer of CYP3A or p-glycoprotein within 3 days of study enrollment. Agents include but are not limited to: carbamazepine, phenytoin, rifampin, and St. John's wart Treatment with any investigational antileukemic agents or chemotherapy agents in the last 7 days before study entry, unless full recovery from side effects has occurred or patient has rapidly progressive disease judged to be life-threatening by the investigator. Prior recent treatment with corticosteroids, hydroxyurea and/or cytarabine (given for cytoreduction) permitted. Use of hydroxyurea or one dose cytarabine to reduce WBC below 25 prior to initiation of study treatment is recommended Pregnant women will not be eligible; women of childbearing potential should have a negative pregnancy test prior to entering on the study and be willing to use effective methods of contraception throughout the study period and for at least 6 months after the last dose of study drugs. Women do not have childbearing potential if they have had a hysterectomy or are postmenopausal without menses for 12 months. In addition, men enrolled on this study should understand the risks to any sexual partner of childbearing potential and should practice an effective method of birth control throughout the study period and for at least 4 months after the last dose of study drugs. Lactating women (or those planning to breastfeed) should not breastfeed during treatment of gilteritinib and for at least 2 months after the last dose of gilteritinib