Inclusion Criteria:

* Age >= 18 years
* Patients must have undergone complete surgical resection of their stage IB (>= 4 cm), II or IIIA NSCLC according to the American Joint Committee on Cancer (AJCC) 7th edition and have had negative surgical margins
* Baseline chest CT must be performed within 1 month (30 days) prior to randomization to ensure no evidence of disease; if clinically indicated, additional imaging studies must be performed to rule out metastatic disease
* Eastern Cooperative Oncology Group (ECOG) performance status 0-1
* Patients must be registered to the ALCHEMIST-SCREEN (ALLIANCE A151216) trial prior to randomization
* Non-squamous tumors must not be positive for EGFR exon 19 deletion or exon 21 L858R mutation (centrally as part of the ALCHEMIST-SCREEN protocol) and ALK rearrangement (centrally as part of ALCHEMIST-SCREEN and/or locally)

* NOTE: if the results of the central EGFR testing are negative, but the ALK testing was not able to be completed by the ALCHEMIST central lab, the ALK status will be considered negative (unless locally positive for ALK rearrangement) and the patient may be considered for enrollment onto EA5142, once PD-L1 results are received and all other eligibility requirements are met
* Tumors must have PD-L1 status tested centrally as part of the ALCHEMIST-SCREEN protocol
* Women must not be pregnant or breast-feeding due to unknown and potentially harmful effects of nivolumab on the developing fetus or child
* All females of childbearing potential must have a blood test or urine study within 2 weeks prior to registration to rule out pregnancy; a female of childbearing potential is any woman, regardless of sexual orientation or whether they have undergone tubal ligation, who meets the following criteria: 1) has not undergone a hysterectomy or bilateral oophorectomy; or 2) has not been naturally postmenopausal for at least 24 consecutive months (i.e., has had menses at any time in the preceding 24 consecutive months)
* Women of childbearing potential and sexually active males must be strongly advised to use an accepted and effective method of contraception or to abstain from sexual intercourse during the treatment period and for 31 weeks after the last nivolumab infusion
* Patients must NOT have uncontrolled intercurrent illness including, but not limited to, serious ongoing or active infection, symptomatic congestive heart failure, unstable angina pectoris, uncontrolled cardiac arrhythmia, or psychiatric illness/social situation that would limit compliance with study requirements
* No prior treatment with an immune checkpoint inhibitor (anti-PD-1, anti-PD-L1, anti-CTLA4 monoclonal antibody)
* Patients must have adequately recovered from thoracic surgery and any administered chemotherapy/radiotherapy at the time of randomization (NOTE: adjuvant chemotherapy and/or radiation is not required)

* Minimum time between date of surgery and randomization is 4 weeks (28 days)
* Maximum time allowed between surgery and randomization:

* 3 months (90 days) if no chemotherapy is administered
* 8 months (240 days) if adjuvant chemotherapy was administered
* 10 months (300 days) if adjuvant chemotherapy and radiation therapy was administered
* Patients must have completed and recovered from any adjuvant chemotherapy 2 or more weeks prior to randomization (6 weeks for mitomycin and nitrosoureas; 4 weeks for post-operative radiation therapy) (NOTE: adjuvant chemotherapy and/or radiation is not required)
* Serum aspartate transaminase (aspartate aminotransferase \[AST\]) and serum alanine transaminase (alanine aminotransferase \[ALT\]) =< 2.5 x upper limit normal (within 2 weeks prior to randomization)
* Total bilirubin =< 1.5 x upper limit of normal (ULN) (except in subjects with Gilbert syndrome who must have a total bilirubin < 3.0 x ULN) (within 2 weeks prior to randomization)
* White blood cell (WBC) >= 2000/uL (within 2 weeks prior to randomization)
* Neutrophils >= 1000/uL (within 2 weeks prior to randomization)
* Platelets >= 100 x 10\^3/uL (within 2 weeks prior to randomization)
* Hemoglobin >= 8 g/dL (within 2 weeks prior to randomization)
* Serum creatinine =< 2 x ULN (within 2 weeks prior to randomization)
* Prior to randomization patients with any non-hematologic toxicity from surgery, chemotherapy and radiation therapy must have recovered to grade =< 1 with the exception of alopecia, ototoxicity and neuropathy
* Patients must not be receiving any other investigational anti-cancer agents while on study
* Patients must not have known or suspected autoimmune disease; subjects with type I diabetes mellitus, hypothyroidism requiring hormone replacement, or skin disorders not requiring systemic treatment are permitted to enroll
* Patients must not have a condition requiring systemic corticosteroids equivalent to > 10 mg prednisone per day or other immunosuppressive medications within 2 weeks of randomization; inhaled, intra-articular, and epidural steroids are permissible
* Patients must not have known interstitial lung disease that is symptomatic or may interfere with the detection or management of suspected drug-related pulmonary toxicity
* Patients must not have a known history of human immunodeficiency virus (HIV), hepatitis B, or hepatitis C infection that is untreated and/or with a detectable viral load
* Patients must not have a history of allergic reactions attributed to compounds of similar chemical or biologic composition to nivolumab