Background: There is a continuous search for healthy food ingredients for dog diets that do not compete with human consumption. Grains, which have been recently claimed to be unsuitable for dogs, are regaining interest. This study aimed to evaluate the effects of rye and triticale as alternatives to wheat on digestion, fecal quality, health, and preference in dogs. Twenty-one Golden Retriever dogs (aged 3–6 years, mean body weight 26 kg) were used. Eighteen dogs (n = 6 per diet) completed the digestibility trial, and 21 dogs participated in the preference test. Dogs were fed diets containing 30% wheat, rye, or triticale, with chicken meal as the animal protein source. Results: Higher dry matter and organic matter digestibility were determined in rye compared to wheat. Crude protein digestion did not differ among grains. Fecal consistency and fecal short-chain fatty acids were similar for all grains. Rye decreased fecal dry matter compared to triticale. Blood urea nitrogen, creatinine, glucose, cholesterol, triglyceride, AST, ALT, and amylase values were not affected by grain type. Dogs’ preferences, determined by their approach to the feed, did not differ according to grain type. Conclusion: Based on these results, there appears to be no contraindication to using rye and triticale as grain sources in extruded dog foods.