Inclusion Criteria:

* Documented informed consent of the participant and/or legally authorized representative
* Agreement to allow the use of archival blood samples and marrow from diagnostic tumor biopsies. If unavailable, exceptions may be granted with study principal investigator (PI) approval
* Eastern Cooperative Oncology Group (ECOG) status =\< 1
* Histologically confirmed AML (not including acute promyelocytic leukemia) or MDS
* Patients with the following diagnoses

* Refractory/relapsed AML by World Health Organization (WHO) classification, who are not candidates for allogeneic stem cell transplantation or potentially curative chemotherapy (Extramedullary disease is allowed).
* MDS by WHO Classification who have failed to respond or relapsed after previous therapies
* Must have a life expectancy of \>= 3 months
* Fully recovered (=\< grade 1) from the acute toxic effects (except alopecia) or complications of prior anti-cancer therapy, including surgery
* Cannot be a candidate for allogeneic hematopoietic cell transplantation (alloHCT) within 90 days of starting treatment on the protocol and should be off pembrolizumab for at least 30 days to become eligible for alloHCT post-protocol therapy
* White blood cells (WBC) =\< 25 x 10\^9/L prior to initiation of venetoclax. Cytoreduction with hydroxyurea prior to treatment and/or during cycles 1 and/or 2 may be required
* Total bilirubin =\< 2 x upper limit of normal (ULN) (unless has Gilbert's disease)
* Aspartate aminotransferase (AST) and alanine aminotransferase (ALT) =\< 2.5 x ULN
* Creatinine clearance of \> 30 mL/min per 24-hour urine test or the Cockcroft-Gault formula
* International normalized ratio (INR) OR prothrombin time (PT) =\< 1.5 x ULN
* Activated partial thromboplastin time (aPTT) =\< 1.5 x ULN
* Left ventricular ejection fraction (LVEF) \>= 50%
* Pulmonary function tests diffusion capacity of the lung for carbon monoxide (DLCO) (adjusted for hemoglobin) \> 50% predicted
* Corrected QT (QTc) =\< 480 ms, Note: electrocardiogram (ECG) (single-read) to be performed within 14 days prior to day 1 of protocol therapy
* Seronegative for human immunodeficiency virus (HIV) antigen (Ag)/antibody (Ab) combo, hepatitis C virus (HCV), and active hepatitis B virus (HBV) (surface antigen negative)

* If positive, hepatitis C ribonucleic acid (RNA) quantitation must be performed
* Meets other institutional and federal requirements for infectious disease titer requirements

* Note: Infectious disease testing to be performed within 28 days prior to day 1 of protocol therapy
* Women of childbearing potential (WOCBP): negative urine or serum pregnancy test
* Agreement by males and females of childbearing potential to use an effective birth control method of low user dependency or abstain from heterosexual activity from 4 weeks prior to first dose of treatment throughout the study treatment period and 3 (males) to 4 (females) months from the last dose of treatment

* Childbearing potential is defined as not being surgically sterilized (men and women) or have not been free from menses for \> 1 year (women only)
* Also, male subjects should refrain from sperm donation from the start of treatment throughout the study treatment period and for 6 months following the last dose of treatment

Exclusion Criteria:

* Previous allogeneic cell transplantation
* Previous treatment with pembrolizumab
* Previously refractory to treatment with decitabine + venetoclax (i.e. progressed through therapy without first attaining at least a partial response)
* Systemic steroid therapy or any other form of immunosuppressive medication
* Received a live-virus or live-attenuated virus vaccination within 30 days of planned treatment start. Administration of killed vaccines is allowed
* Prior treatment with any other anti-programmed cell death protein-1 (anti-PD-1), or PD ligand-1 (PD-L1) or PD ligand-2 (PD-L2) agent or an antibody targeting other immuno-regulatory receptors or mechanisms
* Prior therapy with an anti-CD137, anti-CTLA-4 antibody (including ipilimumab), denosumab or any other antibody or drug specifically targeting T-cell co-stimulation or checkpoint pathways
* Current or planned use of other investigational agents, antineoplastic, biological or chemotherapeutic agents during the study treatment period, or within 4 weeks or five half-lives, whichever is shorter, prior to day 1 of protocol therapy with the following exception:

* Hydroxyurea is allowed prior to treatment with venetoclax and through cycle 2 for control of rapidly progressing leukemia
* Strong or moderate CYP3A4 inducers within 14 days prior to day 1 of venetoclax
* Grapefruit, grapefruit products, Seville oranges (including marmalade containing Seville oranges) or star fruit consumed within 3 days prior to the first dose of venetoclax
* Has received prior radiotherapy within 2 weeks of start of study intervention. Participants must have recovered from all radiation-related toxicities, not require corticosteroids, and not have had radiation pneumonitis. A 1-week washout is permitted for palliative radiation (=\<2 weeks of radiotherapy) to non-central nervous system (CNS) disease
* Concurrent use of corticosteroids (exception: nasal or topical corticosteroids or physiologic levels for steroid replacement are allowed)
* Granulocyte-macrophage colony-stimulating factor (GMCSF) or granulocyte colony stimulating factor (GCSF) within 7 days prior to start of study treatment
* History of allergic reactions attributed to compounds of similar chemical or biologic composition to study agent
* Severe hypersensitivity reaction to treatment with another monoclonal antibody (mAb)
* Active central nervous system (CNS) disease
* The following cardiac conditions:

* Unstable angina
* Congestive heart failure (New York Heart Association \[NYHA\] class III or IV; or class II with a recent decompensation requiring hospitalization or referral to a heart failure clinic within 6 months before screening)
* Acute coronary syndrome and/or revascularization (e.g., coronary artery bypass graft, stent) within 6 months of first dose of study drug Note: Allowed heart conditions are restricted to stable angina, arrhythmia or atrial fibrillation controlled by medication, history of controlled coronary artery disease \> 6 months prior to screening and medically managed
* Pulmonary dysfunction, such as history of non-infectious pneumonitis that required steroids or current pneumonitis or idiopathic pulmonary fibrosis. Note: Allowed pulmonary conditions are restricted to mild chronic obstructive pulmonary disease (COPD), controlled asthma, resolved bacterial or fungal pneumonia, or previous pulmonary embolism (PE) that has been compensated
* Active autoimmune disease that has required systemic treatment in the past 2 years (replacement therapies for hormone deficiencies are allowed)
* Uncontrolled active infection requiring therapy
* Known history of active TB (Bacillus tuberculosis)
* Symptomatic ascites or pleural effusion
* Clinically significant uncontrolled illness
* Females only: Pregnant or breastfeeding
* Any other condition that would, in the investigator's judgment, contraindicate the patient's participation in the clinical study due to safety concerns with clinical study procedures
* Prospective participants who, in the opinion of the investigator, may not be able to comply with all study procedures (including compliance issues related to feasibility/logistics)