A szezon végén visszavonuló középpályás 1972. augusztus 30-án született az Érc-hegység lábánál fekvő Cheb városában. A Nedved família semmiben sem különbözött az akkori cseh átlagtól, a családfő, Václav egy gyárban melózott, s mivel a mama, Ana sem tartozott a felső tízezerhez, így Pavel és nővére nem dúskálhatott a javakban. A Nedved gyerekek így a szocialista Csehszlovákiában szokásos életmód szerint élték mindennapjaikat, jól tanultak, és még a sportolásra is jutott idejük. Pavel azonban nem a jégkorongba habarodott bele, hanem a labdarúgáshoz vonzódott. A feltételek adottak voltak, hiszen Chebnek a Rudá Hvezdá jóvoltából második ligás futballcsapata volt, így Nedved a klub sportiskolájában kezdett el focizni. Az 1950-ben Sokol Sokolovo néven alapított egyesület 1953-tól 1991-ig szerepelt Rudá Hvezdá (azaz Vörös Csillag) néven. A klub tizenhárom szezont töltött a csehszlovák élvonalban, így a későbbi aranylabdást megfelelő körülmények fogadták a Kozeluzská utcai sportpályán.
Az RH Cheb a belügyminisztérium kebelén belül működött, a fővárosi Spartától minden évben a Slavkovi-erdőben lévő városba irányították a hadköteles labdarúgókat. A Lokomotiva stadionban lévő csapattablókon több ismerős arcot lehet felfedezni: Radek Drulák (1982-87 között focizott Chebben), Tomás Skuhravy (1983-85), Pavel Kuka (1987-89), Horst Siegl (1988-90), Michal Hornák (1989-90) képe fogadja az érkezőket. Valamennyien válogatott futballisták lettek később, nem kivétel közülük Pavel Nedved sem.
Az RH-nál folyó szakmai munka magas színvonalára garanciát jelentett egy másik "tablószereplő" személye. Az 1996-ban Európa-bajnoki ezüstérmet nyert cseh válogatott szövetségi kapitánya, Dusan Uhrín 1983-tól 1987-ig és 1989-től 1991-ig irányította a futballcsapatot. A Sparta fiatal pályaedzője sok tapasztalatot szerzett a városban, s nem mellékesen már akkor együtt dolgozhatott későbbi sikercsapata néhány játékosával.