Sixty vacuum-packed beef samples retailed in Germany were investigated for the occurrence of cold-tolerant Clostridium spp. After a storage period at 4 °C for eight weeks, meat juice from all samples was processed for culturing, DNA extraction and SYBR green qPCR for Clostridium species. After that, a previously developed multiplex qPCR, sequence analysis of the 16S rRNA gene, and MALDI-TOF MS were applied in order to identify Clostridium spp. found in samples. Subsequently, 23 samples were found positive for C. frigoriphilum (n = 19), C. estertheticum (n = 2), C. tagluense (n = 1) and C. lacusfryxellense/C. frigoris (n = 1). By using a new multiplex qPCR and a new RFLP method developed in this study, a further 15 meat juice samples were revealed to be contaminated with C. algidicarnis. With some samples being co-contaminated with two different species, 53% (n = 32) of all investigated vacuum-packed beef samples were found to be positive for cold-tolerant clostridia. This is the first report of detection and identification of C. algidicarnis in meat samples in Germany and Central Europe.