Background: Cronobacter sakazakii is a new emerging foodborne bacterial pathogen associated with severe lethal diseases such as meningitis, necrotizing enterocolitis, and septicemia in infants and neonates. Powdered infant formula milk (PIFM) has been recognized as one of the main transmission vehicles and contaminated sources of this pathogen. This study aimed to investigate the prevalence rate, genotypic and phenotypic antibiotic resistance profile, and clonal relatedness of C. sakazakii strains isolated from 364 PIFM samples collected from Tehran city, Iran. Methods: Culture-based methods, Kirby–Bauer disk diffusion antibiotic resistance testing, conventional Polymerase Chain Reaction (PCR), and Enterobacterial Repetitive Intergenic Consensus PCR (ERIC-PCR) assays were used in this study to detect and characterize the C. sakazakii isolates. Results: We isolated 25 C. sakazakii strains from PIFM samples (6.86%). The isolates were highly resistant to amoxicillin-clavulanic acid, amoxicillin, ampicillin, cefoxitin, cefepime, erythromycin, ceftriaxone, ciprofloxacin, and chloramphenicol and susceptible to gentamicin, tetracycline, norfloxacin, and azithromycin antibiotics. The blaCTX-M-1 gene was detected in 96% of the isolates. The isolates were categorized into eight distinct clonal types using the ERIC-PCR method, showing a high genetic diversity among the isolates. However, there was a significant correlation between the genotypic and phenotypic antibiotic resistance properties of the isolates. Conclusions: Novel microbial surveillance systems for detecting multi-drug-resistant C. sakazakii are required to control the contamination of this foodborne pathogen in infant foods.