Inclusion Criteria:  Written (signed and dated) informed consent for both pre-screening and the main trial and capable of co-operating with any investigational medicinal product (IMP) administration and follow-up. Histologically or cytologically proven Stage IIIB, IIIC or IV squamous NSCLC or Stage IIIB or IV non-squamous NSCLC scheduled to receive pembrolizumab and chemotherapy as standard of care at the time of enrolment or randomisation. Patients can receive up to two cycles of SoC pembrolizumab in combination with chemotherapy prior to enrolment or randomisation to the trial.  NSCLC patients with no prior immune checkpoint inhibitor therapy prior to the pembrolizumab they are receiving in combination with chemotherapy at time of enrolment or randomisation.  For non-squamous NSCLC patients, the patient has not received previous systemic therapy for advanced/metastatic disease. Completion of treatment with chemotherapy and/or radiotherapy as part of neoadjuvant therapy is allowed as long as the therapy was completed at least 6 months prior to the diagnosis of recurrent locally advanced or metastatic disease. For squamous NSCLC patients, the patient has not received previous cytotoxic chemotherapy for advanced/metastatic disease. Completion of treatment for earlier stage disease with chemotherapy with or without radiotherapy as part of neoadjuvant/concurrent/adjuvant therapy is allowed as long as therapy was completed at least 6 months prior to the diagnosis of recurrent locally advanced or metastatic disease. Have at least one measurable lesion according to RECIST v1.1. PD-L1 status between 1% and 50% tumour proportion score. Archival tumour tissue or new biopsy expressing MAGE-A3 as demonstrated by RT PCR. Life expectancy of at least 12 weeks Eastern Cooperative Oncology Group (ECOG) performance status of 0 or 1.  Haematological and biochemical indices within the ranges shown below. These measurements should be performed to confirm the patient's eligibility.  Haemoglobin (Hb) ≥90 g/L (no prior transfusion within last 4 weeks) OR ≥100 g/L (transfusion within last 4 weeks) Absolute neutrophil count (ANC) ≥1.5×10^9/L (growth factor support (G-CSF) is allowed when used as part of routine supportive therapy for Standard of Care) Platelet count ≥100×10^9/L International normalized ratio (INR) AND prothrombin time (PT) OR Activated partial thromboplastin time (aPTT) ≤1.5 × ULN unless participant is receiving anticoagulant therapy as long as PT or aPTT is within therapeutic range of intended use of anticoagulants Bilirubin ≤1.5 x upper limit of normal (ULN) OR < 3 x ULN in the presence of documented Gilbert's Syndrome (unconjugated hyperbilirubinaemia) Alanine aminotransferase (ALT) or aspartate aminotransferase (AST) ≤3.0 x ULN OR ≤5.0 x ULN in presence of liver metastases Calculated creatinine clearance (using the Cockcroft & Gault [C&G] formula) ≥50 mL/min or serum creatinine ≤1.5 x ULN  Aged 18 years or over at the time pre-screening consent is given.  Exclusion Criteria:  For non-squamous NSCLC patients, patients who have received previous systemic therapy for advanced/metastatic disease prior to the pembrolizumab they are receiving in combination with chemotherapy at time of enrolment or randomisation. Completion of treatment with chemotherapy and/or radiotherapy as part of neoadjuvant therapy is allowed as long as the therapy was completed at least 6 months prior to the diagnosis of recurrent locally advanced or metastatic disease.  For squamous NSCLC patients, patients who have received previous cytotoxic chemotherapy for advanced/metastatic disease prior to the pembrolizumab they are receiving in combination with chemotherapy at time of enrolment or randomisation. Completion of treatment for earlier stage disease with chemotherapy with or without radiotherapy as part of neoadjuvant/concurrent/adjuvant therapy is allowed as long as therapy was completed at least 6 months prior to the diagnosis of recurrent locally advanced or metastatic disease.  Previous therapy with an anti-PD-1, anti-PD-L1, or anti-PD-L2 agent or with an agent directed to another stimulatory or co-inhibitory T cell receptor (e.g., anti-CTLA-4, OX 40, anti-CD137). This does not include the immune checkpoint inhibitor patients receive in combination with chemotherapy commencing during screening prior to enrolment or randomisation to the trial. Current or prior malignancy which could affect safety or efficacy assessment of the IMP or compliance with the protocol or interpretation of results. Patients with curatively-treated non-melanoma skin cancer, non-muscle-invasive bladder cancer, or carcinomas-in-situ are eligible. Known active central nervous system (CNS) metastases and/or carcinomatous meningitis. Patients with symptomatically active brain metastases or leptomeningeal metastases. Patients with previously treated brain metastases may participate provided they are radiologically stable, i.e., without evidence of progression for at least 4 weeks by repeat imaging (note that the repeat imaging should be performed during trial screening), clinically stable and without requirement of steroid treatment for at least 14 days prior to first dose of study treatment.  Women of child-bearing potential (or are already pregnant or lactating). However, those patients who meet the following points are considered eligible:  Have a negative serum or urine pregnancy test before enrolment or randomisation and; Agree to use two forms of contraception (one effective form plus a barrier method) [oral, injected or implanted hormonal contraception and condom; intra-uterine device and condom; diaphragm with spermicidal gel and condom] or agree to sexual abstinence , effective from the first administration of ChAdOx1-MAGEA3-NYESO, throughout the treatment phase of the trial and for six months afterwards..  Male patients with partners of child-bearing potential. However, those patients who meet the following points are considered eligible:  They agree to take measures not to father children by using a barrier method of contraception (condom plus spermicide) or to sexual abstinence6 effective from the Cycle 3 Day 1 of SoC treatment, throughout the treatment phase of the trial and for six months afterwards. Men with partners of child bearing potential must also be willing to ensure that their partner uses an effective method of contraception for the same duration for example, hormonal contraception, intra uterine device, diaphragm with spermicidal gel or sexual abstinence. Men with pregnant or lactating partners must be advised to use barrier method contraception (for example, condom plus spermicidal gel) to prevent exposure to the foetus or neonate. Major thoracic or abdominal surgery from which the patient has not yet recovered. Patients who have undergone other types of surgery which the Chief Investigator (CI) and Sponsor agree would not compromise patient safety on trial are eligible. Electrocardiogram (ECG) with clinically significant abnormalities or with QTcF interval (QT corrected using Fridericia's formula) >480 msec. At high medical risk because of non-malignant systemic disease including active uncontrolled infection. Historically known to be serologically positive for hepatitis B or human immunodeficiency virus (HIV). Patients with previous Hepatitis C exposure but no current infection are eligible to participate. Has an active autoimmune disease that has required systemic treatment in the past 2 years (i.e., with use of disease modifying agents, corticosteroids or immunosuppressive drugs). Replacement therapy (e.g., thyroxine, insulin, or physiologic corticosteroid replacement therapy for adrenal or pituitary insufficiency) is not considered a form of systemic treatment and is allowed. Has received AZD1222 (previously named ChAdOx1-nCoV-19) vaccine within six weeks of commencing chemotherapy and an immune checkpoint inhibitor. Has received any other live vaccination within four weeks before enrolment or randomisation to the trial. Examples of live vaccines include, but are not limited to, the following: measles, mumps, rubella, varicella/zoster, yellow fever, rabies, Bacillus Calmette-Guerin (BCG), and typhoid vaccine. Seasonal influenza vaccines for injection are generally killed virus vaccines and are allowed; however, intranasal influenza vaccines (e.g., FluMist®) are live attenuated vaccines and are not allowed. Has a diagnosis of immunodeficiency or is receiving chronic systemic steroid therapy (in dosing exceeding 10 mg daily of prednisone equivalent) or any other form of immunosuppressive therapy within 7 days prior the first dose of study drug. Has undergone prior allogeneic hematopoietic stem cell transplantation within the last 5 years. Participants who have had a transplant greater than 5 years ago are eligible as long as there are no symptoms of graft versus host disease (GVHD). Has previously experienced severe hypersensitivity (≥Grade 3) to an immune checkpoint inhibitor, ChAdOx1 or MVA vaccines and/or any of their excipients. History of a severe allergy to eggs or history of severe allergic reaction to any previous vaccination. Is a participant or plans to participate in another interventional clinical trial, whilst taking part in this Phase I/IIa trial. Participation in an observational trial or interventional clinical trial which does not involve administration of an IMP and which would not place an unacceptable burden on the patient in the opinion of the Investigator and Medical Advisor would be acceptable. Any other condition, which in the Investigator's opinion, would not make the patient a good candidate for the clinical trial.