(1) BACKGROUND/OBJECTIVES: The Paleolithic diet has been receiving media coverage in Australia and claims to improve overall health. The diet removes grains and dairy, whilst encouraging consumption of fruits, vegetables, meat, eggs and nuts. Our aim was to compare the diet to the Australian Guide to Healthy Eating (AGHE) in terms of compliance, palatability and feasibility; (2) SUBJECTS/METHODS: 39 healthy women (age 47 ± 13 years, BMI 27 ± 4 kg/m²) were randomised to an ad-libitum Paleolithic (n = 22) or AGHE diet (n = 17) for 4-weeks. A food checklist was completed daily, with mean discretionary consumption (serves/day) calculated to assess compliance. A 12-item questionnaire was administered post intervention to assess palatability and feasibility; (3) RESULTS: The AGHE group reported greater daily consumption of discretionary items (1.0 + 0.6 vs. 0.57 + 0.6 serves/day, p = 0.03). Compared to the AGHE group, the Paleolithic group reported a significantly greater number of events of diarrhoea (23%, 0%, p = 0.046), costs associated with grocery shopping (69%, 6% p < 0.01) and belief that the diet was not healthy (43%, 0% p < 0.01); (4) CONCLUSIONS: Compliance to both diets was high but the potential side effects and increased cost suggest that the Paleolithic diet may not be practical in clinical/public health settings. Further studies are required to assess longer term feasibility.