Zielomyśl powstał około XIII w., a pierwsza wzmianka w źródłach historycznych dotycząca miejscowości pochodzi z roku 1403. Osada składała się wówczas z kilku gospodarstw usytuowanych wzdłuż drogi, w pobliżu niewielkiego jeziora. Od średniowiecza była własnością biskupów poznańskich i wchodziła w skład klucza pszczewskiego. Po drugim rozbiorze Polski wieś, podobnie jak resztę majątku biskupiego, skonfiskowały władze pruskie i przekazały księciu Hohenlohe. Zielomyśl od początku należał do parafii Pszczew. W XIX wieku na ziemie pszczewskie zaczęli przybywać innowiercy, stąd blisko połowę mieszkańców Zielomyśla stanowili wtedy protestanci. W 1865 roku 27 rolników z Zielomyśla wzięło udział w fundacji kościoła ewangelickiego w Pszczewie. W 1900 roku w Zielomyślu, dzięki staraniom mieszkańców, konsekrowano kościół rzymsko-katolicki p.w. św. Józefa. Właścicielem Zielomyśla w tym czasie był Rudolf Hoene z Lipowca. Po zakończeniu I wojny światowej wieś przyłączono do Niemiec, zaledwie 1,5 km od granicy z Polską. W 1944 roku Niemcy zbudowali tu fortyfikacje stanowiące część Trzcielskiej Pozycji Przesłaniania. Po II wojnie światowej Zielomyśl wrócił w granice Rzeczypospolitej.
Na zachód od wsi wznosi się Góra Trębacza – wyniesienie będące doskonałym punktem widokowym na najbliższą okolicę.