Methods, systems, and computer readable media for over the air provisioning of soft cards on devices with wireless communications capabilities are disclosed. According to one method, a soft card provisioning application is instantiated on a device with wireless communications capabilities. A card number for a soft card desired to be provisioned on the device is obtained from a user of the device. An issuer identification number retrieved from the card number is communicated to a provisioning configuration server over an air interface. A provisioning issuer server network address is obtained from the provisioning configuration server based on the issuer identification number. The provisioning information server is connected to, and card-issuer-specific challenge information is obtained therefrom. The challenges are presented to the user, and the user's responses to the challenges are received. A connection is made to the provisioning issuer server corresponding to the network address. The challenge responses are communicated to the provisioning issuer server. Soft card image data and personalization data, where the personalization data includes personalized embossed and pre-printed data, are received from the provisioning issuer server over the air interface. The soft card is provisioned for use on the device based on the data received over the air interface.