Území Všestar, které se nachází u potoka Melounky a staré obchodní stezky na Hořice a Jičín, bylo osídleno již v mladší době bronzové, což podporuje řada archeologických nálezů. Roku 1908 došlo na návrší na poli Ladislava Ryby k objevu malého slezského pohřebiště z mladší doby bronzové. Královéhradecké městské historické muzeum zde vykopalo 5 popelnicových hrobů. Kromě zbytků nádob se našla řada bronzových milodarů (plochý kroužek, závěrek a jehlice). Asi 20 m na sever došlo k objevu jámy naplněné zemí, která byla smíchána s dřevěným uhlím a popelem. Jednalo se nejspíše o jámu, v níž byl spálen člověk. V bývalé cihelně obchodníka a poštmistra F. L. Součka byly před rokem 1880 nalezeny zlaté závitky a na zahradě při domu čp. 3 roku 1881 množství rozbitých nádob, jelení parohy a několik bronzových předmětů. Podle všeho se jednalo o sídliště z mladší doby bronzové. Většina všech dochovaných archeologických nálezů z Všestar je z období slezskoplatěnické kultury a k jejich objevu došlo na poli Jana Hroneše směrem k Rozběřicím.
Samo pojmenování obce mělo vzniknout ze slova všestaři, což znamenalo: všichni krásní, asi podle kroje nebo způsobu strojení, alespoň tak tvrdí Antonín Profous. Nejstaršími známými majiteli nebo spoluvlastníky Všestar byli: královéhradecký měšťan Zdislav a po něm královéhradecká měšťanka Kristina, kteří sem podávali faráře v roce 1360, resp. roku 1366. Na počátku 15. století byli zdejšími pány Dubánkové z Duban. V roce 1401 prezentovali Vilém Dubánek z Duban st. a ml. Za faráře do Všestar krňovického faráře Václava, ale spolupatron kostela Roblík, královéhradecký měšťan a pán na Bříze, jež byla do Všestar přifařená, prezentoval kněze Hanku. Spor mezi nimi se dostal až do Říma a ukončen byl roku 1408 tím, že Václav ustoupil a Hanek slíbil, že požádá druhého patrona Viléma ml. Dubánka, který sídlil v Bělečku, aby mu v držení kostela nepřekážel. Ten nového kněze prezentoval již v témže a následujícím roce. Roku 1410 prodal navíc 14 kop úroků, 2 selské dvory, jichž užívali Matějík a Jakub řečený Zakša, a podací kostelní, pokud mu náleželo, Kateřině z Hradce Králové, manželce Jakuba Zakšy, za 69 kop grošů. Kateřina je poté zastavila svému manželovi. V roce 1419 Vilém ml. Dubánek prodal za 253 ½ kopy grošů, co ještě ve Všestarech vlastnil, Jiřímu z Hradce Králové. Roku 1454 se Martin a Jiří, synové Jakuba a Kateřiny Zakšových, uvázali po smrti svého otce ve dvůr poplužní a dvůr selský ve Všestarech s příslušenstvím. Martin je připomínán ještě v roce 1456. Na počátku 16. století již Všestary náležely městu Hradci Králové, které tu prodalo za 400 kop grošů Alexandru, bratru Absolona na Dobříkově, dvůr a role. Ale Alexandr ve své poslední vůli z roku 1506 požádal královéhradeckou obec, aby tento statek přijala zase zpět, což se následně i stalo. Ještě v témže roce koupil tento dvůr za 308 kop grošů královéhradecký měšťan Jan Puška. Roku 1547 byly Všestary městu Hradci Králové zkonfiskovány králem Ferdinandem I. Zdejší kmetcí dvůr byl v témže roce prodán Janu z Pernštejna a roku 1548 jeho syny Janem, Jaroslavem, Vojtěchem a Vratislavem Zdeňku Zárubovi z Hustířan a na Cerekvici. Zbytek vsi byl v roce 1549 navrácen královéhradeckým farám a špitálům. Roku 1550 město Hradec Králové odkoupilo od krále Ferdinanda I. vrchnost nade všemi statky, jež náležely k různým záduším, takže se Všestary staly opět poddanou vesnicí královéhradecké obce. Po bitvě na Bílé hoře byly městu opět odňaty, ale v roce 1628 navráceny zpět. Posledním farářem podobojí byl v letech 1617-1622 Jan Gregory Hradecký. Později byly Všestary přifařeky ke královéhradeckým minoritům. Roku 1642 byly všechny zdejší statky dílem pobořené a ostatek vsi pustý. Spálen byl též mlýn, který stával na místě nynějšího čp. 40. Zmizel též rybník, na němž dnes stojí domy čp. 41-49. V roce 1654 byli ve Všestarech 4 sedláci, 1 chalupník, 3 zahradníci a 1 selské stavení rozbité a pusté, od něhož sedláci rolí užívali. Roku 1671 zde měla královéhradecká obec svůj pivovar a ten zanikl někdy v letech 1827-1828. V roce 1687 byla zřízena stálá farní expozitura, obsazovaná královéhradeckými minority. Prvním administrátorem se stal P. Augustin Forberský. Kolem roku 1767 byly děti vyučovány Josefem Rychlovským z Poniklé v chalupě čp. 40. Později se vyučovalo v hospodě čp. 25 a v roce 1770 byla postavena dřevěná škola, v níž od roku 1786 učil stálý učitel. V roce 1776 byly domy očíslovány. V letech 1768-1769 se připomíná zdejší městský dvůr, který byl roku 1783 rozdělen mezi poddané. Stával na místě stavení čp. 6-12. V roce 1786 byly Všestary přifařeny ke Kuklenám. Roku 1793 byla vystavěna zděná škola, která byla o 3 roky později nahrazena novou. V roce 1798 byla postavena nová fara. Roku 1807 došlo k opětovnému očíslování zdejších domů. O 6 let později tu leželo pruské a ruské vojsko. V letech 1819-1820 byla stavěna státní silnice od prachárny ve Svobodných Dvorech přes Všestary do Lípy. V roce 1842 byl kostel královéhradeckým stavitelem Františkem Kurzem znovu postaven. V letech 1847-1848 byla postavena nová školní budova a roku 1848 nová fara.
Díky prozatímnímu zřízení obecnímu se staly Všestary v roce 1849 svobodnou politickou i katastrální obcí. V letech 1852-1890 fungovala cihelna F. L. Boučka. 10. října 1862 se začaly půjčovat knihy z nově vzniklé knihovny. Roku 1864 vyhořelo 5 stavení. O rok později bylo založeno Živnostenské společenstvo. 3. července 1866 se octla obec v bitevní vřavě prusko-rakouské války. V kostele, ve škole a ve stodolách u čp. 23, 38, 42, 43 a 50 byl vojenský lazaret a ve stodole u čp. 39 pitevna. 4. listopadu 1866 navštívil obec císař František Josef I. V témže roce podlehlo choleře 35 lidí. Roku 1866 byla také založena Občanská záložna. V roce 1867 byl zřízen poštovní úřad a roku 1881 telegrafní stanice. V roce 1872 založil L. Souček a spol. akciovou společnost k závodu obchodu se střižním zbožím. O 2 roky později byl založen spolek Společný mláticí stroj ve Všestarech, který byl po dvouleté existenci přeměněn v družstvo. Roku 1876 vznikl včelařský spolek. V roce 1882 později byla stavěna obchodní dráha a při té příležitosti byla zřízena železniční stanice. Roku 1885 byl otevřen nový hřbitov. V letech 1886-1887 byla postavena nová školní budova. V roce 1894 byla založena Čtenářsko-hospodářská beseda a o 6 let později Spořitelní a záložní spolek. 21. července 1901 byla zavedena v obvodu všestarského poštovního úřadu přespolní pošta. Roku 1903 byla stavěna okresní silnice ke Střezeticím a odbočka od ní do Rosnice. V letech 1907-1914 působil v obci Okrašlovací spolek. 20. května 1908 udeřil blesk do kostelní věže a srazil z jejího vrcholu kamenný kříž. V roce 1910 byla postavena obecní váha. Roku 1912 došlo k založení Vodního družstva a TJ Sokol. V témže roce byl do Všestar zaveden z Hradce Králové elektrický proud. Roku 1913 byla stavěna okresní silnice ke Světí. V následujícím roce byla provedena regulace Melounky a do obce přišlo 17 uprchlíků z Haliče, z nichž 7 bylo roku 1915 přestěhováno do Světí. V roce 1917 byla Pomocným komitétem pro péči o polské uprchlíky v Hradci Králové otevřena ve Všestarech polská škola. Téhož roku byl založen SDH. Z front 1. světové války se nevrátilo 12 zdejších mužů.
V roce 1918 bylo založeno Družstvo pro rozvod a zužitkování elektrické síly v hospodářství a živnostech. V letech 1925-1926 došlo k rozšíření školy směrem k faře a přístavbě patra na dosavadní školu. V roce 1941 byla zahájena výstavba elektrické rozvodny. 11. prosince 1941 vyskočil člen zdejší sokolské jednoty Hynek Jirouš z okna věznice v Hradci Králové při výslechu, těžce se zranil a zemřel. 30. listopadu 1947 byla otevřena nová sokolovna. V letech 1952-1953 došlo k přístavbě školní budovy čp. 57. Roku 1953 vzniklo JZD, které bylo k 1. květnu 1960 připojeno k JZD Bříza. V letech 1960- 1980 byla postupně vybudována kanalizace. 1. ledna 1973 bylo nově ustaveno JZD Nový směr Hradecka Všestary. V letech 1979-1981 bylo postaveno v akci Z zdravotní středisko. V roce 1985 byla zřízena vlastivědná stezka Po bojišti Chlum 1866. Roku 1986 bylo předáno do užívání nové nákupní středisko a dům služeb. V letech 1993-1997 probíhala plynofikace obce. V roce 1996 byl vybudován krytý bazén. 26. srpna 2004 vykolejil v železniční stanici nákladní vlak, který zdemoloval část nádraží. Výpravčí, který měl v tu dobu v železniční stanici službu, spáchal po nehodě sebevraždu. V letech 2009- 2012 proběhla výstavba Archeoparku pravěku ve Všestarech, který byl budován od roku 1997 jako Pravěká vesnice. V letech 2013-2015 byla provedena nová kanalizace.
Nejvýznamnější místní pamětihodností je klasicistní kostel Nejsvětější Trojice, který byl postaven v letech 1842-1843 podle návrhu královéhradeckého stavitele Františka Kurze, u něhož stojí renesanční věž s gotickými prvky z původního chrámu. Za zmínku též stojí řada pomníků z prusko-rakouské války roku 1866, např. žulová stéla na pískovcovém soklu rakouského nápředníka Franze Köglera II. od osmiliberní pěší baterie č. 10 prvního dělostřeleckého pluku z roku 1894, kterou věnoval František Waldek; pískovcová typová pyramida s nápisem „Zde odpočívá 7 rakouských a 30 pruských a 90 kroků odtud 150 rakouských vojáků“ z roku 1902, nahrazující původní kříž typu č. 302. Dále nutno jmenovat: hřbitovní kříž z roku 1885 a pamětní desku na budově železniční stanice, která byla odhalena v roce 1946 na památku přednosty zdejší železniční stanice Hynka Jirouše. Více o zdejším archeoparku zde:
http://archeoparkvsestary.cz.