Dnešní pojmenování obce reaguje na skutečnost, že byla po odsunu německého obyvatelstva osídlena Čechy, kteří sem přišli z Českého Malína na Volyni. Starší název Frankštát, užívaný do roku 1947, byl přejat z německého Frankstadt odvozeného od osobního jména Frank ve významu "město Frankovo". Od roku 1973 je částí Nového Malína osada Plechy (viz Dolní Studénky). Pečetním znamením
Nového Malína byla stavba kostela.

Původní katastr Nového Malína o výměře 1980 hektarů (v roce 1992 jen 1964 hektary) se většinou nachází v Šumperské kotlině, ale zalesněným výběžkem na východě zasahuje do kopců Hraběšické hornatiny až ke Kamennému vrchu (952 m). Pod ním pramení potok směřující do Desné a podle něj se táhne obec, jejíž střední nadmořská výška je 340 m. Na západní okraj Nového Malína souvisle navazuje osada Plechy. Ta již leží v údolí Desné a má střední nadmořskou výšku 317 m. Obcí prochází železniční trať ze Šumperka do Uničova a Olomouce, silnicemi je spojena se Šumperkem, Hrabišínem, Mladoňovem i Hraběšicemi.

Od poloviny 19. století se počet obyvatel obce dynamicky zvyšoval z 1 715 v roce 1850 na 2330 v roce 1900 (v 253 domech) a kulminoval v roce 1910, kdy ve Frankštátě žilo dokonce 2539 obyvatel. Z 2326 obyvatel v roce 1930 bylo jen 236 Čechů. Po druhé světové válce bylo německé obyvatelstvo odsunuto, ale atraktivní poloha Nového Malína v bezprostřední blízkosti okresního města lákala nové osídlence, mezi nimiž byla většina volyňských Čechů. V roce 1950 v obci žilo v 390 domech 1478 osob. Při posledním sčítání v roce 1991 bylo v Novém Malíně zjištěno 1765 obyvatel, 615 bytů a 454 domů, v části Plechy 192 obyvatel a 52 domů.

Frankštát se poprvé připomíná v písemných pramenech k roku 1350. Byla zde tvrz a dvůr a v průběhu 14. a 15. století se po Frankštátě psali příslušníci několika rodů. V roce 1398 bylo městečko zapsáno držiteli hradu Rabštejna loupeživému rytíři Pročkovi z Bouzova, v roce 1480 si na ně dělal nárok známý majitel zábřežského panství Jiří st. Tunkl. Od roku 1496 náležel Frankštát k bludovskému panství pánů ze Žerotína. V době žerotínské byl Frankštát jmenován několikrát městečkem, avšak v roce 1569 byl spolu s jiným zbožím prodán městu Šumperku a od roku 1583 byl opět uváděn jako ves. V roce 1643 byl vydrancován Švédy, ale přesto zde podle lánového rejstříku hospodařilo v roce 1677 107 usedlíků, z nichž bylo 72 sedláků a 35 chalupníků. V průběhu 16. až 19. století se frankštátští dostali se svou šumperskou vrchností do několika sporů, jejichž předmětem byla zejména výše robotních povinností. V roce 1834 bylo v městečku již 220 domů a 1580 obyvatel. Již v polovině 18. století zde měla vrchnost papírnu.

Fara byla v městečku jistě v 16. století, za třicetileté války zanikla (od roku 1728 tu byl knězexpozita) a byla obnovena v roce 1784 jako kuracie (od roku 1843 opět farnašt). O škole, která byla patrně druhou nejstarší na Šumpersku, máme zprávu už z roku 1869 a její vznik patrně souvisel s opakovaným povýšením Frankštátu na městečko.

Po roce 1848 se stal Frankštát součástí politického a soudního okresu Šumperk. Vedle zemědělství se začalo v městečku rozvíjet hrnčířství a průmysl stavebních hmot, využívající ložiska hrnčířské hlíny v okolí. V roce 1880 zahájila výrobu Pudilova a později Berkova továrna na šamotové a hliněné zboží, která v meziválečném období zaměstnávala až 80 dělníků. Cihelna založená v roce 1893 náležela od roku 1927 firmě Žďárský. Ve druhé polovině 19. století pracovala továrna na hřebíky, od roku 1874 likérka, v meziválečném období mlýn, menší tkalcovna a výrobna dřevěných tkalcovských člunků. Šumperský velkostatek měl ve Frankštátě lesní revír. Mnoho zdejších obyvatel nacházelo uplatnění v šumperských továrnách.

V politickém životě městečka se zpočátku projevovalo soupeření německých stran sociálně demokratické, křesťanskosociální a agrární s nacionálně orientovanými stranami a v roce 1935 bezkonkurenčně dominovala Henleinova Sudetoněmecká strana. Německá škola rozšířená na šestitřídní byla doplněna pokračovací školou a pro děti z českých rodin začalo od roku 1919 vyučování v menšinové jednotřídní a od třicátých let dvojtřídní škole. Ta byla zrušena po začlenění Frankštátu do Sudet v roce 1938.

Po druhé světové válce nabýval Nový Malín stále výrazněji charakter šumperského předměstí. Zemědělské družstvo tu bylo založeno už v roce 1950, v roce 19S6 převzalo i malé JZD Hraběšice a v roce 1976 se sloučilo s JZD Bludov. Krátce pokračovala tradiční výroba hrnčířského zboží, dodnes je v provozu cihelna. V roce 1990 byla v Novém Malíně železniční stanice, pošta, úplná základní škola, kino, tři prodejny smíšeného zboží, prodejna potravin a tři pohostinství.

Frankštátským rodákem je historik Clemens A. Janetschek (1857 až 1908) a geolog dr. Hugo Schon (1899 až 1975). Památkově chráněný barokní kostel Narození P. Marie byl postaven v roce 1705 a v roce 1811 upravován. V okolí kostela jsou patrny valy, jejichž přesné stáří není známo.