Some tumors are difficult to treat with chemotherapy or radiation. One of the reasons is that areas of the tumor do not have many blood vessels, which makes it difficult for drugs to reach those areas. One way that researchers have recently tried to overcome this problem is by injecting special kinds of bacteria into the tumors. These bacteria have been genetically changed to remove the chemicals that are poisonous to humans, but are still able to cause tumor cells to break down and die. The idea is that these bacteria may be able to assist chemotherapy drugs in fighting cancer.

The goal of this clinical research study is to find the highest tolerable dose of one of these bacterial therapies (Clostridium novyi-NT spores) that can be given in combination with pembrolizumab to patients with advanced solid tumors. The safety of this drug will also be studied, as well as whether it can help to control the disease.

This is an investigational study. Clostridium novyi-NT is not FDA approved or commercially available. It is currently being used for research purposes only. Pembrolizumab is FDA approved for the treatment of melanoma and different types of head and neck and non-small cell lung cancers. It is investigational to use these drugs in combination with each other in various types of advanced cancers.

The study doctor can describe how the study drugs are designed to work.

Up to 18 participants will be enrolled in this study. All will take part at MD Anderson.

Study Drug Dose Levels:

If you are found to be eligible to take part in this study, you will be assigned to a dose level of Clostridium novyi-NT based on when you join this study. Up to 4 dose levels will be tested. Up to 6 participants will be enrolled at each dose level. The first group of participants will receive the lowest dose level of Clostridium novyi-NT. Each new group will receive a higher dose than the group before it, if no intolerable side effects were seen. This will continue until the highest tolerable dose of Clostridium novyi-NT is found, or all 4 dose levels are filled.

During the study, the supporting company (BioMed Valley Discoveries, Inc.) and study doctors may increase the number of patients in a dose group based on the available study results. This will not change your participation while on study.

All participants will receive the same dose level of pembrolizumab.

Study Drug Administration:

You will receive pembrolizumab by vein over about 30 minutes on Day 0 and then every 3 weeks for up to 12 months.

Clostridium novyi-NT will be injected into the tumor on Day 8. This is the only injection into the tumor you will receive. Your doctors may use an x-ray or ultrasound to help place the needle into the tumor. You will be in the hospital for 7 days to check for side effects, or possibly longer if your study doctor thinks it is needed. You will be able to go home if you have no signs or symptoms of infection. If the study doctor thinks it is needed (for example, based on your tests or any infection symptoms), you may need to return to the hospital at a later time.

Starting on Day 15, you will take an antibiotic (doxycycline) by mouth 2 times a day for the rest of your life to lower the risk of further growth of Clostridium novyi-NT. This is because the study drug is a changed form of bacteria. If you miss a dose or forget to take doxycycline, take it as soon as you can. If it is almost time for your next dose, wait until then to take it and you should skip the missed dose. Do not take an extra dose to make up for a missed dose.

If the doctor thinks it is needed, you will also take additional antibiotics, piperacillin/tazobactam and metronidazole. The antibiotic that is given and the length of time you need to take it will depend on your reaction to the study drug. You should still continue to take doxycycline. Your doctor will discuss this with you. You may receive piperacillin/tazobactam by vein over about 30 minutes and metronidazole by vein over about 30-60 minutes as often as your doctor tells you to, until your doctor thinks it is acceptable for you to change to taking the antibiotics by mouth. In some cases, if you need to receive antibiotics by vein for more than a week or two, your doctor may ask you to have a central venous catheter placed. A central venous catheter is a sterile flexible tube that will be placed into a large vein while you are under local anesthesia. Your doctor will explain this procedure to you in more detail, and you will be required to sign a separate consent form.

You may also be given other standard drugs to help decrease the risk of side effects. You may ask the study staff for information about how the drugs are given and their risks.

Length of Study Participation:

You may receive 1 dose of Clostridium novyi-NT and receive pembrolizumab every 3 weeks for up to 12 months. You will then have 12 months of follow-up after you receive the last dose of pembrolizumab. You will be taken off study early if the disease gets worse, if you have intolerable side effects, or if you are unable to follow study directions.

Your participation on the study will be over after the Month 12 post-dosing follow-up visit.

If you leave the study early, you or your family will be called every 3 months for up to 12 months to see how you are doing. These calls should last less than 30 minutes each time.

Study Visits and Calls:

For your safety, you must stay within 45 minutes driving distance from an emergency room and also have a caregiver available for at least 28 days after you receive your dose of Clostridium novyi-NT spores.

If an abscess (a swollen area of infection that contains pus) forms in the tumor and it needs to be drained, the study doctor may decide to collect some of the drainage for research tests to study the infection and test your immune system response.

Tumor biopsy samples (described below) may be collected at different times than listed, or not at all, depending on the inflammation around the tumor, the amount of tissue available, or how easily it can be collected.

On Days 0 and 1:

• You will have a physical exam.
• You will have an EKG to check your heart function.
• You will have a biopsy sample collected from the target tumor before you receive pembrolizumab. The tumor sample will be used for biomarker testing, including genetic biomarkers and to check your body's inflammatory and immune responses to the study drug. Biomarkers are found in the blood/tissue and may be related to your reaction to the study drug. The type of biopsy you have will depend on the location of the disease. The study staff will describe this procedure in more detail, including its risks.
• If you can become pregnant, you will have a blood (about 1 teaspoon) or urine pregnancy test.

On Day 8:

• You will have a physical exam.
• Blood (about 4 ½ tablespoons) will be drawn for routine tests, to find out how long the Clostridium novyi-NT spores and bacteria stay in your body, and to measure your risk for bacteremia at 1 hour and 12 hours after the study drug dose.

On Days 9-15 daily:

• You will have a physical exam.
• Blood (about 1½ teaspoons) will be drawn for routine tests.
• You will have either a CT scan or MRI to check the status of the disease (Day 15 only).
• If you have any skin lesions, photographs will be taken of these lesions.

After you leave the hospital and during the first 28 days after you receive Clostridium novyi-NT spores, the study staff will call you 1 time each day on the days you do not have study visits. You will be asked how you are doing. The calls should last less than 30 minutes each time.

On Days 18 and 25, you will have a physical exam.

On Days 21 and 28:

• You will have a physical exam.
• Blood (about 1½ teaspoons) will be drawn for routine tests.

On Days 35:

• You will have a physical exam.
• Blood (about 4 ½ tablespoons) will be drawn for routine tests, to check your body's inflammatory and immune system response to the study drug, to find out how long the Clostridium novyi-NT spores and bacteria stay in your body, and to measure your risk for bacteremia.

At Weeks 6, 9, 15, 24, 39, 45, and 48, you will have a physical exam.

Every 3 weeks beginning with Week 6, blood (about 1 tablespoon) will be drawn for routine testing.

Every 6 weeks beginning with Week 6:

• You will have either a CT scan or MRI to check the status of the disease.
• If you have any skin lesions, photographs will be taken of these lesions.

At Week 9, blood (about 1 teaspoon) will also be drawn for HLA testing.

At Week 12, you will have a tumor tissue biopsy sample collected of the injected tumor and a non-injected tumor for biomarker testing and to help learn how your body is responding to the study drug.

At Weeks 9, 24, 33 and 48, blood (about 4 ½ tablespoons) will be drawn for routine tests, to check your body's inflammatory and immune system response to the study drug, to find out how long the Clostridium novyi-NT spores and bacteria stay in your body, and to measure your risk for bacteremia.

The tests and procedures may be repeated anytime the doctor thinks it is needed.

End of Study Visit:

After you stop receiving the study drug(s):

• Blood (about 3½ tablespoons) will be drawn for routine tests, to check your body's inflammatory and immune system response to the study drug, to find out how long the Clostridium novyi-NT spores and bacteria stay in your body, and to measure your risk for bacteremia.
• You will have either a CT scan or MRI to check the status of the disease.
• If you have any skin lesions, photographs will be taken of these lesions.

Follow Up Visit:

About 30 days after your last dose of pembrolizumab:

• You will have a physical exam.
• Blood (about 1 tablespoon) and urine will be collected for routine tests.
• You will have either a CT scan or MRI to check the status of the disease. It will be repeated every 3 months for up to 12 months.
• If you have any skin lesions, photographs will be taken of these lesions.

After the last follow-up visit, you or a family member will be called every 3 months for an additional year and asked about how you are doing. Each call should last about 15 minutes.

Inclusion Criteria:

1. Diagnosis of an advanced solid tumor malignancy. There must be a target tumor which is measureable, palpable or clearly identifiable under ultrasound or radiographic guidance and amenable to percutaneous injection of C. novyi-NT spores. The targeted lesion must have a longest diameter >/= 1 cm and < 12 cm and be measurable as defined by RECIST 1.1 criteria. The target lesion must not be located in either the thoracic, abdominal or pelvic cavities or in the brain. There must be no clinical, no functional, and no radiographic evidence of bone involvement at the site of the target lesion.
2. History of prior treatment with at least one line of systemic anticancer therapy, when an approved systemic therapy is available, and no curative option is available for continued treatment.
3. At least 4 weeks have elapsed since the completion of major surgery, and the patient has fully recovered from this surgery and any post-surgical complications.
4. Patient must have adequate organ function as indicated by the following laboratory values. Hematological: Absolute neutrophil count (ANC) >/=1,500/mcL; Platelets >/=100,000/mcL; Hemoglobin >/=9g/dL or >/= 5.6 mmol/L. Renal: Serum creatinine </= 1.5 X upper limit of normal (ULN. Hepatic: serum total bilirubin </= 1.5 X ULN OR Direct bilirubin </= ULN for patients with total bilirubin levels > 1.5 ULN; AST (SGOT) and ALT (SPGT) </= 2.5 X ULN OR </= 5 X ULN for patients with liver metastases. Coagulation: International Normalized ration (INR) or Prothrombin Time (PT) </= 1.5 X ULN unless patient is receiving anticoagulant therapy as long as PT of PTT is within therapeutic range of intended use of anticoagulants; Activated partial Thromboplastin Time (aPTT) </= 1.5 X ULN unless patient is receiving anticoagulant therapy as long as PT of PTT is within therapeutic range of intended use of anticoagulants.
5. Eastern Cooperative Oncology Group (ECOG) performance status of 0 or 1.
6. Patient is at least 18 years of age.
7. Patient is capable of giving informed consent.
8. Female patient of childbearing potential has a negative urine or serum pregnancy test. If the urine test is positive or cannot be confirmed as negative, a serum pregnancy test will be required. The serum pregnancy test must be negative for the patient to be eligible.
9. Patient of childbearing potential is using either 2 adequate barrier methods or a barrier method plus a hormonal method of contraception to prevent pregnancy or to abstain from heterosexual activity throughout the study, starting with Visit 1 through 120 days after the last dose of study therapy. Approved contraceptive methods include 2 of the following barrier methods or one barrier method combined with a hormonal contraceptive: a. Intra uterine device, diaphragm with spermicide, cervical cap with spermicide, male condoms, or female condom with spermicide. Spermicides or condoms alone are not an acceptable method of contraception. b. Male patients must agree to use an adequate method of contraception starting with the first dose of study drug through 120 days after the last dose of study therapy.
10. Patient has no significant valvular heart disease (trace or mild valvular stenosis or regurgitation is allowed).
11. Patient is able to stay within 45 minutes driving time of an emergency room for 28 days after dosing with C. novyi-NT.
12. The patient has a caregiver for 28 days after dosing with C. novyi-NT.
13. Patient has a tumor sample from C. novyi-NT planned injected tumor lesion (newly obtained biopsy) for PD-L1 and immunologic response assessments. Patients must submit the tumor sample during screening at a central pathology laboratory.

Exclusion Criteria:

1. Patient who has had chemotherapy, radiation therapy, or biological cancer therapy within four weeks prior to the first dose of study drug, or who has not recovered to CTCAE Grade 1 or better from the AEs due to cancer therapeutics administered more than four weeks earlier.
2. Patient is currently participating or has participated in a study of an investigational agent or using an investigational device within 30 days of the first dose of study drug. (A patient in the survival Follow up phase of an investigational agent where no further treatment is expected is eligible).
3. Patient is on any systemic corticosteroid therapy within one week before the planned date for first dose of treatment or on any other form of immunosuppressive medication.
4. Documented primary brain malignancy or brain metastases.
5. Patient previously had a severe hypersensitivity reaction to treatment with another mAb.
6. Patient has an active autoimmune disease or a documented history of autoimmune disease or syndrome that requires systemic steroids or immunosuppressive agents. Patients with vitiligo or resolved childhood asthma/atopy would be an exception to this rule. Patients that require intermittent use of bronchodilators or local steroid injections would not be excluded from the study. Patients with hypothyroidism stable on hormone replacement will not be excluded from the study.
7. Patient has an active infection requiring systemic therapy.
8. Patient has known history of Human Immunodeficiency Virus (HIV) (HIV ½ antibodies).
9. Patient has a known history of or is positive for Hepatitis B (HBsAg reactive) or Hepatitis C (HCV RNA [qualitative] is detected).
10. Patient is pregnant or breastfeeding, or expecting to conceive or father children within the projected duration of the study.
11. Patient has received a live vaccine within 30 days prior to first dose.
12. Patient has a foreign body which in the opinion of the treating investigator could be difficult to manage in case of infection.
13. Clinically significant pleural effusion.
14. Clinically significant pericardial effusion, circumferential pericardial effusion, or any effusion greater than 1.0 cm at any location around the heart.
15. Need for ongoing treatment with an immunosuppressive agent.
16. History of solid organ transplantation (with the exception of a corneal transplant > 3 months prior to screening).
17. History of an ischemic insult in the previous 12 months (myocardial infarction, cerebral vascular accident, ischemic tissue from injury, transient ischemic attack).
18. History of a significant medical illness deemed by the PI as unsuitable for the trial. For example: i. Symptomatic congestive heart failure ii. Psychiatric Illness/social situation that may make study dangerous iii. Unstable angina pectoris.
19. History of asplenia.
20. Antibiotic allergies that would preclude treatment for a C. novyi-NT infection.
21. Treatment with antibiotics within 2 weeks (14 days) of dosing.
22. Oxygen saturation (Sp02) of less than 95% on room air.
23. Mean arterial blood pressure (BP) of less than 70 mmHg.
24. Glasgow Coma Score of less than 15.
25. History of (non-infectious) pneumonitis that required steroids or current pneumonitis.