Česká strana části pohraničního hvozdu spolu s loukami zvanými “Napolickach”, na nichž bylo v roce 1265 založeno město Polička, patřila před rokem 1200 litomyšlskému klášteru. V písemných pramenech se tento místní název objevuje v listině z roku 1167, v níž král Vladislav II. přijímá do své ochrany premonstrátskou kanonii v Litomyšli a potvrzuje jí statky a práva. Výrazu Napolickach bylo obvykle rozuměno "na políčkách", tedy na malých polích; při tomto chápání by však výraz "na políčkách" po přechodu do jednotného čísla dal tvar Políčko, a nikoliv Polička. Všichni významní čeští badatelé zabývající se původem místních názvů se ztotožňují s názorem, že slovo polička je zdrobnělinou slova police s významem rovina nebo rovinka. Existuje ovšem i další názor, že jméno Police a tedy i Polička, které je jeho zdrobnělinou, by mohlo označovat vypálené místo v lesích. Takový význam mohlo mít podstatné jméno police, jehož slovní základ pol- znamená dřeva ožehávaná sáláním ohně. Název města v podobě Polička se ustálil teprve od 14. století.

Polička byla založena v rámci velkorysého plánu Přemysla Otakara II. vytvořit soustavu měst při obchodní stezce spojující Prahu s moravskými centry (stezka není v pramenech označována žádným jménem - nejpříhodnějším by však patrně podle jejího směru bylo “moravská” a nikoliv Trstenická, jak ji v polovině 19. století nepříliš šťastně nazval Hermenegild Jireček). V 60. letech 13. století při této stezce takřka současně vznikají města Kouřim, Kolín, Čáslav, Chrudim, Vysoké Mýto a jako poslední na české straně i Polička; zjevným důvodem založení bylo posílení královské moci v tomto nejvzdálenějším cípu východních Čech.Zakládací listinu města Poličky vydal Přemysl Otakar II., král český, vévoda rakouský a štýrský a markrabě moravský, dne 27. září 1265. Lokátorem, tedy vlastním organizátorem založení, byl Konrád z Lewendorfu, který je v literatuře obvykle, avšak mylně vydáván za lokátora řady dalších královských měst. Jediným jeho dalším nesporným založením je tak pouze s městem sousedící ves Lewendorf (později Laubendorf, počeštěně Limberk, dnes Pomezí). Odměnou za jeho námahu i značné riziko mu byl úřad městského rychtáře a další výhody. Původ nových osadníků zůstává zahalen tajemstvím; soudí se však, že pocházeli ze severního Německa, neboť město se mělo řídit magdeburským, tedy severoněmeckým městským právem.K středně velkému městu bylo přiměřeno 50 lánů polí z celkového okrsku 800 lánů. Obyvatelům vesnic v tomto okrsku se Polička stala vrchností. Od okolních vesnic, jejichž založení pravděpodobně předcházelo založení města, neboť to vzhledem ke svým hospodářským i jiným funkcím nemohlo existovat bez zemědělského zázemí, se Polička lišila nejen výsadami, ale i výstavbou a hradbami. Původní záměr zakladatele - vytvořit uzavřený, plně funkční městský celek - se však zřejmě dařilo plnit jen velmi zvolna. Limitujícím prvkem zde byl hlavně nedostatek osadníků, a to i přesto, že novým obyvatelům byly slibovány nejrůznější výhody: město obdrželo výsadu mílového práva (v okruhu jedné míle od města nesměla být na úkor jeho obyvatel provozována výdělečná činnost), měšťané byli na 20 let osvobozeni od placení veškerých dávek a navíc mohli od kupců putujících po zemské stezce, která byla po založení města vedena přes Poličku, vybírat mýto.

V prvních desetiletích své existence sdílela Polička většinou osud nedalekého hradu Svojanova. V roce 1284 byla sice správa Poličky a přilehlého území králem Václavem II. svěřena pražskému biskupovi Tobiáši z Bechyně, ale již o rok později spravoval toto území Záviš z Falkenštejna, který pojal za manželku Kunhutu, vdovu po Přemyslu Otakaru II.; manželé si za své sídlo zvolili právě hrad Svojanov. V roce 1307 byl však osud města Poličky určen na další staletí, když byla českým králem Rudolfem I. Habsburským správa města a z ní plynoucí důchody postoupena jeho manželce Alžbětě (známější pod jménem Eliška Rejčka). Polička se tak stala věnným městem královniným. Počet věnných měst se postupem času zvyšoval až na konečných devět (Dvůr Králové nad Labem, Hradec Králové, Chrudim, Jaroměř, Mělník, Nový Bydžov, Polička, Trutnov a Vysoké Mýto) a tato kategorie existovala až do zániku rakousko-uherské monarchie v roce 1918, byť byly v posledních desetiletích povinnosti měst k jejich královnám více než formální - nicméně poličští na tomto titulu do poslední chvíle okázale lpěli.

Velkou událost pro města vždy představovaly návštěvy panovníků a nejinak tomu bylo i v Poličce. V dubnu 1336 se zde na čtyři dny zastavil Jan Lucemburský a na přelomu července a srpna roku 1356 zde se svým doprovodem minimálně tři dny pobyl Karel IV. Strategický význam Poličky na pomezí Čech a Moravy byl zdůrazněn vybudováním mohutných hradeb, které z Poličky vytvořily skutečnou pohraniční pevnost. Zlepšení životního prostředí v Poličce přineslo privilegium Karla IV. z roku 1360, kterým povolil město vydláždit a po osm let užívat práv, “jež i jiným městům ohledně dláždění byla povolena”. V období vlády Karla IV. byla také zřejmě završena přestavba dosud dřevěných, případně hrázděných domů na kamenné.Úměrně vzrůstu bohatství vzrůstalo i sebevědomí měšťanského patriciátu, nejbohatšího starousedlého měšťanstva, který se stále více začal prosazovat v městské správě na úkor výsadního městského rychtáře; o tom svědčí i opis Sigillum civium de Politz (Pečeť měšťanů Poličky) na nejstarší známé městské pečeti z roku 1362, dokazující, že byla používána jménem měšťanů, a nikoliv jen z vůle rychtáře. Dalším projevem sebevědomí měšťanů byla stavba radnice uprostřed náměstí jako symbolu měšťanské samosprávy.Na předměstí, kde rostl počet neplnoprávných občanů, kteří náleželi přímo pod správu města a tedy pod pravomoc městské rady, ale i v samém městě sílil již ve 14. století vliv českého živlu. Na pražské univerzitě se po skončení studií ve významných funkcích uplatnili studenti původem z Poličky: v roce 1388, v době pronikajícího vlivu reformních náboženských hnutí, zde působil mistr Matyáš z Poličky a v letech 1410-11, tedy v době po vydání Kutnohorského dekretu, zaručujícího Čechům na univerzitě převahu, byl děkanem fakulty svobodných umění Petr z Poličky.

Na počátku husitských válek stála Polička, jakožto věnné město, na straně královny. Když však na jaře roku 1421 vytáhl hejtman Jan Žižka z Trocnova spolu s pražany do východních Čech, otevřela Polička, stejně jako Chrudim a Vysoké Mýto, své brány a přistoupila k Pražskému městskému svazu. Již na podzim roku 1421 však město za ne zcela vyjasněných okolností vyplenila jedna z částí uherského vojska Zikmunda Lucemburského; starý letopisec dokonce uvádí zřejmě zveličený počet “1300 zmordovaných”. Polička sice setrvala v táboře pražanů, ale do dalšího průběhu husitské revoluce výrazněji nezasáhla. Po definitivní porážce radikálních husitů v roce 1436 pak zástupci poličských měšťanů, stejně jako jiných měst, vzdali v Jihlavě hold Zikmundu Lucemburskému a dozoru nad městem se opět ujal královnin podkomoří.
Husitská revoluce přispěla k dovršení českého charakteru města - byl vypuzen německý katolický patriciát a Polička se stala ryze českým městem, hlásícím se ke kališnickému vyznání. Z nejstarší městské knihy známe složení městské rady k roku 1432; jména konšelů až na výjimky znějí zvučně česky a v dalších letech se jak mezi konšely, tak mezi měšťany setkáváme již jen se jmény českými.