V místech kde jsou Všestary, bydleli lidé již v době předhistorické, jak dokazují předhistorické památky tu nalezené. Roku 1908 tady bylo objeveno malé slezské pohřebiště z mladší doby bronzové. Jméno Všestar vzniklo z Všestaři, co znamenalo: všichni krásní, asi dle kroje nebo způsobu strojení. Osada Všestary založena byla při potoku Melounce a staré obchodní cestě, která Hradec Králové spojovala s Hořicemi a Jičínem. Lidé tu bydleli v mladší době bronzové, o čemž svědčí objevené tu popelnicové pohřebiště rázu slezského.

Nejstaršími a známými majiteli Všestar nebo aspoň části byli měšťan hradecký Zdislav a po něm Krisitna, měšťanka hradecká, z nich onen roku 1360 a to 1366 faráře sem podávali. Na počátku 15. století byli pány V. Dubánkové z Duban roku 1410 prodal 14 kop úroků, dva selské dvory, jichž užívali Matějík a Jakub reč. Zakša a podací kostelní, pokud mu náleželo, Kateřině z Hradce Králové, manželce dotčeného Jakuba Zakšv. Kateřina pak zastavila je svému manželu. Roku 1419 týž Vilém Dubánek prodal co ještě ve V. měl, Jiřímu z Hradce Králové.

Roku 1454 Martin a Jiřík, synové Jakuba Zakšy a manželky jeho Kateřiny, po smrti svého otce uvázali se ve dvůr poplužní a dvůr selský ve V. s příslušenstvím. Martin připomíná se ještě roku 1456. Počátkem 16. století náležely V. městu Hradci Králové které prodalo tu za 400 kop gr. Alexandru bratru Absolona na Dobříkově dvůr a role. Ale Alexandr v poslední vůli své roku 1506 učiněné žádal obce hradecké, aby ten statek zase zpět přijala, což se i stalo. Téhož roku od obce hradecké koupil onen dvůr Jan Puška, měšťan hradecký. Roku 1547 byly městu Hradci Králové V. králem Ferdinandem I. skonfiskovány. Nějaký dvůr kmetcí (selský) ve V. prodán byl téhož roku Janu z Pernštejna a roku 1548 syny jeho Janem, Jaroslavem, Vojtěchem a Vratislavem Zdeňku Zárubovi z Hustířan, pánu na Cerekvici. Ostatek Všestar byl Ferdinandem I. roku 1549 vrácen některým farám a špitálům města Hradce Králové.

Roku 1550 město Hradec Králové odkoupilo od krále Ferdinanda I. vrchnost nade všemi statky, jež k různým zduším náležely, tedy i nad Všestary. Ty se staly opět jako byly dříve poddanou vesnicí obce královohradecké.
Po bitvě na Bílé hoře roku 1620 V. Hradci Králové opět skonfiskovány, ale roku 1628 vráceny.

DALŠÍ INFORMACE: http://www.vsestary-obec.cz