Background: Erectile dysfunction (ED) is one of the manifestations of long COVID-19 and in most cases has an endothelial and neurogenic nature. Many experimental and clinical investigations have revealed the high efficacy of transcutaneous electrical nerve stimulation (TENS) of the pudendal nerve and low-level laser therapy (LLLT) in the treatment of ED. Purpose: To compare LLLT and TENS, and investigate the dynamics of their efficacy when combined in the treatment of patients with post-COVID-19 ED using the International Index of Erectile Function-15 (IIEF-15). Materials and Methods: This interventional, randomized controlled trial enrolled 82 patients with ED following COVID-19. All patients had their first ED diagnosis after COVID-19 within one month of the onset of respiratory symptoms. The duration of patients’ ED was not less than six months, but less than one year. Patients were divided into four groups, one of which received sham LLLT and TENS (n = 20). The remaining patients underwent effective treatment using LLLT (n = 21), TENS (n = 21), and combined LLLT and TENS (n = 20). To study the effectiveness of the treatment, IIEF-15 and an assessment of tactile sensation in the genital area before and after the treatment, as well as 3 months after the end of the treatment, were used. Results: Both LLLT and TENS had a significant effect in improving erectile function, of 38% (p ≤ 0.01) and 27% (p ≤ 0.01), respectively. The improvement in erectile function after LLLT was higher than after TENS by 8.2% (p ≤ 0.05), but the combination of these methods exceeds the result of using LLLT alone by 20% (p ≤ 0.01). The reduction in hypoesthesia after LLLT did not exceed 17.4% (p ≤ 0.05). However, after TENS, the reduction in hypoesthesia reached 48.7% (p ≤ 0.01), and with a combination of the two methods, it reached 60.9% (p ≤ 0.01). Treatment outcomes in LLLT, TENS, and LLLT + TENS groups were stable for 3 months. Conclusions: According to IIEF-15 dynamics, LLLT and TENS are both very beneficial in treatment of post-COVID-19 ED, with LLLT showing a moderately better outcome than TENS. LLLT and TENS were found to have significant positive therapeutic effects on orgasm, sexual desire, and sexual satisfaction, among other aspects of sexual function. Nevertheless, the combination of LLLT and TENS proved to be much more successful in enhancing all IIEF domains, expanding the therapeutic effect spectrum, and improving the TENS effect following LLLT application. Only after TENS did genital hypoesthesia reliably regress, and the effect was amplified when TENS and LLLT were combined.