Nemanja Vidič sa narodil v meste Užice, robotníkovi v továrni na meď vo výslužbe a bankovej úradníčke. Nemanja začal hrávať futbal v siedmich rokoch po boku staršieho brata Dušana v miestnom klube Jedinstvo Užice. Rýchlo napredoval a v dvanástich rokoch prešiel do klubu Sloboda Užice.