A method and apparatus configured for updating vehicle software using over-the-air (OTA) may include extracting first format difference data and second format difference data, corresponding to a first format and a second format of an update target software image, respectively, comparing the first format difference data and the second format difference data, determining a format of difference data as a transmission target, based on the comparison result, and transmitting the determined format of difference data to an update target vehicle terminal through a wireless network. Accordingly, it is advantageous to minimize the amount of transmitted data while vehicle software is updated using OTA.