Jméno vsi je zřejmě odvozeno od osobního jména Paloňa, jehož původ a výklad je však již různý (např. osoba s velkou hlavou, spojení se slovesem páliti). Je to jedna z mála obcí, která si v posledních stoletích udržela administrativní samostatnost. V pečetním poli Palonína je štít s kosmým břevnem, na němž spočívá zvláštní znamení, které připomíná srdce nabodené na rožeň.

Palonínský katastr s rozlohou 574 hektarů poměrně úrodné půdy se rozkládá v nejjižnějším cípu okresu, při jeho hranici s okresem Olomouc. Ves sama má protáhlý tvar západně od dřívější hlavní silnice z Olomouce do Loštic a Mohelnice, kterou však nahradila v posledních letech východněji vybudovaná ko-munikace dálničního typu. Protože jde o západní okraj údolí řeky Moravy a jižní cíp tzv. Mohelnické brázdy, má ves i okolí poměrně malou nadmořskou výšku kolem 272 m. Palonín si udržoval spíše menší, ale velmi stabilní počet obyvatel. V roce 1900 zde bylo zjištěno 84 domů a 582 obyvatel. Protože šlo o českou obec (v roce 1930 jen tří Němci), došlo tu po roce 1945 pouze k poklesu na 402 obyvatel ve 107 domech v roce 1950 a nakonec na 358 osob ve 106 obydlených domech venkovského typu v roce 1991 .

Katastr Palonína byl osídlen již v pravěku. V 9. století vznikla na jižním okraji vsi slovanská osada, která existovala až do poloviny 13. století. První písemná zmínka je z roku 1353. Byly zde dva poplužní dvory. O několik desítek let později byla tato ves již spojována s Moravičany, tj. především s kartuziány z Tržku u Litomyšle, potom z Dolan a nakonec z Olomouce. Po zrušení kartuziánského kláštera v Olomouci Josefem II. roku 1782 připadl také Palonín k panství Doubravice a v tomto rámci setrval až do roku 1848. Roku 1834 měla ves 72 domů a 520 obyvatel a již asi od roku 1815 zde byla škola.

Po zrušení poddanství se Palonín dostal do soudního okresu Mohelnice a politického okresu Zábřeh. Byla to bohatá a pokročilá zemědělská vesnice. Ne náhodou právě zde vznikl již v roce 1869 čtenářský spolek a roku 1893 tu byla založena družstevní mlékárna, jedna z prvních na celé Moravě. Bylo logické, že zde po roce 1918 ve volbách vítězila agrární strana. V roce 1938 patřila ves k těm obcím, které nebyly po mnichovské dohodě obsazeny německým vojskem, takže druhou světovou válku prožila v rámci soudního a politického okresu Litovel.

Po roce 1945 se samozřejmě ani Palonín nevyhnul všem tehdejším změnám. Nakonec bylo i zde v roce 1956 založeno JZD, které se však již v roce 1960 spojilo s družstvem v Lošticích. Škola v místě byla zrušena, a tak v roce 1990 zůstal jenom kulturní dům, jeden obchod a pohostinství.

Na palonínské škole působil v letech 1871 až 1888 národní a vlastivědný pracovník a spisovatel Jakub Lolek, rodák z Lipinky, a narodil se zde jeho syn, pozdější akademický malíř Stanislav Lolek (1873 až 1936), známý jako výtvarný inspirátor Lišky Bystroušky. Poněkud méně známý je další rodák, česko-německý spisovatel, Antonín Smital (1863 až 1897), který však působil hlavně v Praze a ve Vídni. V obci je zachováno a památkově chráněno několik typických zemědělských usedlostí (čp. 3, 9, 1 l, 32, 33 a 36).