Example systems and methods for automated cover song identification are disclosed. An example apparatus includes at least one memory, machine-readable instructions, and one or more processors to execute the machine-readable instructions to at least execute a constant Q transform on time slices of first audio data to output constant Q transformed time slices, binarize the constant Q transformed time slices to output binarized and constant Q transformed time slices, execute a two-dimensional Fourier transform on time windows within the binarized and constant Q transformed time slices to output two-dimensional Fourier transforms of the time windows, generate a reference data structure based on a sequential order of the two-dimensional Fourier transforms, store the reference data structure in a database, and identify a query data structure associated with query audio data as a cover rendition of the audio data based on a comparison of the query and reference data structures.