Background: Non-melanoma skin cancer (NMSC) takes up a substantial fraction of dermatological and plastic surgical outpatient visits and surgeries. NMSC develops as an accumulated exposure to UV light with the face most frequently diagnosed. Method: This retrospective study investigated the risk of complications in relation to full-thickness skin grafts (FTSG) or local flaps in 607 patients who underwent facial surgery and reconstruction at a high-volume center for facial cancer surgery at a tertiary university hospital. Results: Between 01.12.2017 and 30.11.2020, 304 patients received reconstructive flap surgery and 303 received FTSG following skin cancer removal in the face. Flap reconstruction was predominantly performed in the nasal region (78%, n = 237), whereas FTSG reconstruction was performed in the nasal (41,6%, n = 126), frontal (19.8%, n = 60), and temporal areas (19.8%, n = 60), respectively. Patients undergoing FTSGs had a significantly higher risk of hematoma (p = 0.003), partial necroses (p < 0.001), and total necroses (p < 0.001) compared to flap reconstruction. Age and sex increased the risk of major complications (hematoma, partial or total necrosis, wound dehiscence, or infection) for FTSG, revealing that men exhibited 3.72 times increased risk of major complications compared to women reconstructed with FTSG. A tumor size above 15 mm increased the risk of hematoma and necrosis significantly. In summary, local flaps for facial reconstruction after skin cancer provide lower complication rate compared with FTSGs, especially in elderly and/or male patients. The indication for FTSG should be considered critically if the patient’s tumor size and location allow for both procedures.