Most fruits are paleo, except for banana and melon. However, some would argue that all fruit is paleo! So, use your best judgement and stick to whatever fruit you want. Berries are completely safe though!