In Rwanda, information on antibiotic resistance in food animals is scarce. This study was conducted to detect and phenotypically characterize antibiotic-resistant Escherichia coli and Salmonella in feces of cattle, goats, pigs, and poultry in the East province of Rwanda. We isolated non-type-specific (NTS) E. coli and Salmonella using plain culture media. In addition, we used MacConkey agar media supplemented with cefotaxime at 1.0 μg/mL and ciprofloxacin at 0.5 μg/mL to increase the probability of detecting E. coli with low susceptibility to third-generation cephalosporins and quinolones, respectively. Antibiotic susceptibility testing was performed using the disk diffusion test. Among 540 NTS E. coli isolates, resistance to tetracycline was the most frequently observed (35.6%), followed by resistance to ampicillin (19.6%) and streptomycin (16.5%). Percentages of NTS E. coli resistant to all three antibiotics and percentages of multidrug-resistant strains were higher in isolates from poultry. All isolated Salmonella were susceptible to all antibiotics. The sample-level prevalence for resistance to third-generation cephalosporins was estimated at 35.6% with all third-generation cephalosporin-resistant E. coli, expressing an extended-spectrum beta-lactamase phenotype. The sample-level prevalence for quinolone resistance was estimated at 48.3%. These results provided a baseline for future research and the development of integrated surveillance initiatives.