Factors influencing melanoma survival include sex, age, clinical stage, lymph node involvement, as well as Breslow thickness, presence of tumor-infiltrating lymphocytes based on histological analysis of primary melanoma, mitotic rate, and ulceration. Identification of genes whose expression in primary tumors is associated with these key tumor/patient characteristics can shed light on molecular mechanisms of melanoma survival. Here, we show results from a gene expression analysis of formalin-fixed paraffin-embedded primary melanomas with extensive clinical annotation. The Cancer Genome Atlas data on primary melanomas were used for validation of nominally significant associations. We identified five genes that were significantly associated with the presence of tumor-infiltrating lymphocytes in the joint analysis after adjustment for multiple testing: IL1R2, PPL, PLA2G3, RASAL1, and SGK2. We also identified two genes significantly associated with melanoma metastasis to the regional lymph nodes (PIK3CG and IL2RA), and two genes significantly associated with sex (KDM5C and KDM6A). We found that LEF1 was significantly associated with Breslow thickness and CCNA2 and UBE2T with mitosis. RAD50 was the gene most significantly associated with survival, with a higher level of expression associated with worse survival.