In this paper, a random frequency diverse array-based directional modulation with artificial noise (RFDA-DM-AN) scheme is proposed to enhance physical layer security of wireless communications. Specifically, we first design the RFDA-DM-AN scheme by randomly allocating frequencies to transmit antennas, thereby achieving 2-D (i.e., angle and range) secure transmissions, and outperforming the state-of-the-art 1-D (i.e., angle) phase array (PA)-based DM scheme. Then we derive the closed-form expression of a lower bound on the ergodic secrecy capacity (ESC) of our RFDA-DM-AN scheme. Based on the theoretical lower bound derived, we further optimize the transmission power allocation between the useful signal and artificial noise (AN) in order to improve the ESC. Simulation results show that: (1) our RFDA-DM-AN scheme achieves a higher secrecy capacity than that of the PA-based DM scheme; (2) the lower bound derived is shown to approach the ESC as the number of transmit antennas N increases and precisely matches the ESC when N is sufficiently large; and (3) the proposed optimum power allocation achieves the highest ESC of all power allocations schemes in the RFDA-DM-AN.